【算法】任意模数 NTT 原理 -boshi

在两年前,我学习了快速傅里叶变换。当时有许多的问题没能透彻地理解。 在半年前,我接触到了任意模数 NTT,但是当时只背了个板子,没有弄懂它的原理。 今天,隔壁机房一个高二的大佬点醒了我,我突然就明白任意模数 NTT 究竟再干啥了。 任意模数 NTT 原理 当我们处理模数为任意 $10^9$左右质数的 阅读更多…

【娱乐向】如何造飞机 -boshi

简介 飞行一直是人类的梦想。 六百多年前,万户进行了人类历史上第一次对飞行的探索。 一百二十多年前,李林达尔进行了人类历史上第一次固定翼滑翔机的飞行。 一百多年前,莱特兄弟制造了世界上第一架完全受控的固定翼动力飞机,并且成功试飞。 八十年前,人类历史上第一架喷气式飞机诞生在德国。 一年多前,bosh 阅读更多…

【算法】单调栈——ljh736371592

单调栈 ——单调递增或单调减的栈,跟单调队列差不多,但是只用到它的一端,利用它可以用来解决一些 ACM/ICPC 和 OI 的题目,如 RQNOJ 的诺诺的队列等。 · 功能: 利用单调栈,可以找到从左/右遍历第一个比它小/大的元素的位置 · 模拟: 递增;1,5,2,7,3. 1:1 2:1,5 阅读更多…

【题解】「清华集训 2017」小 Y 和恐怖的奴隶主 状压/期望 DP+矩阵优化 loj2325 —Qiuly

青一的电脑,为你点赞! 卡常真恶心。 发现恐怖的奴隶主数量的上限 $k$ 和恐怖的奴隶主血量的上限 $m$ 都特别小,考虑状压当前所有恐怖的奴隶主。由于每一个恐怖的奴隶主没有不同,我们只需要记下每个不同的血量的恐怖的奴隶主的个数即可。 设 $f_{i,a,b,c}$ 表示还剩 $i$ 次攻击,当前局 阅读更多…