AGC005F Many Easy Problems
AtCoderLuogu分析设要求的东西是 $f_i$，考虑怎么求这个东西。可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但是它确实是 NTT 模数。代码// =================================== // author: ...
标签 FFT & NTT 下的文章
- 首页
- FFT & NTT
洛谷4199 万径人踪灭
LuoguBZOJ分析下文中默认字符串的下标从 $0$ 开始。可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。后面的就是 manacher 板子，考虑怎么求前面的。设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1$，累加起来即可...
Educational Codeforces Round 75 题解
Broken Keyboard如果某一段相同的字符长度为奇数，那么这个字符一定是正常的。代码Binary Palindromes一个长度为偶数的回文串一定有偶数个 $1$，一个长度为奇数的回文串可以有任意个 $1$。检查 $1$ 的奇偶性，如果为偶数则答案为 $n$；否则，如果有长度为奇数的回文串则答案为 $n$，否则答案为 $n-1$。代码Minimize The Integer注意到奇偶...
洛谷3779 [SDOI2017]龙与地下城
LuoguLOJgjh 与地下城分析一种 FFT 做法考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。（大概）可以理解成概率生成函数卷积？然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。一种定积分做法首先要知道中心极限定理的一个推论：设有 $n$ 个独立同分布的随...
洛谷5401 [CTS2019]珍珠
LuoguLOJ分析orz laofu首先题目要求的其实就是方案数。设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有显然也是一个卷积的形式。于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。总结：这是一道好题，可是我...
CQOI2018简要题解
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ，然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵树定理。代码交错序列首先推式子： $x^ay^b=(n-y)^ay^b=\sum\limits_{i...
洛谷5293 [HNOI2019]白兔之舞
LuoguLOJ分析orz laofu先看 $n=1$ 的情况。为了方便，设 $a=w_{1,1}$ 。设 $f_i$ 表示跳 $i$ 步的答案，显然有 $f_i=a^i{n\choose i}$ 。那么有 显然是一个卷积的形式，那么直接 $\mathrm{MTT}$ 实现卷积即可。$n\leq 3$ 的情况实际上就是扩展到了矩阵上，推式子的过程是一样的。具体实现及细节见代码。代码不知道为什...
洛谷5339 [TJOI2019]唱、跳、rap和篮球
LuoguBZOJLOJ分析考虑容斥，计算至少 $i$ 堆人讨论 cxk 的方案数。这个方案数等于点 $i$ 堆人出来的方案数乘上剩下的人随便排的方案数。前面那个东西很容易算，就是 $\dbinom{n-3i}i$ 。考虑后面这个东西怎么算。首先有可重集的排列公式： $\large\frac{n!}{a_1!a_2!...a_k!}$ 。考虑枚举每种的人数，那么这一部分的方案数就是 后面显然...