多项式-生成函数-FFT-NTT-个人总结

# 临时数组一定要清空！ **FFT可用于处理字符集较小的有通配符的匹配（kmp）问题** ### FFT的题关键在于找到“子结构”  ### URAL 1996&万径人踪灭 可以用01序列上的FFT解决一些字符串问题，比如B从A的每一个位置开始，有多少个匹配的位置。或者求以一个点为中心的对称位置的个数。 ### CF827E 这道题，我们要求出含有?（0或1中一个）和01的字符串的border集合（循环节）。 比如循环节为k，那么字符串的下标应该mod k循环。但是FFT只能处理下标差为定值，于是我们先求出固定差下是否相同，然后$O(n/k)$枚举k的倍数check即可。 ### 某道题 现有N个数$a_1,a_2,\cdots,a_N$。对于每一个$a_k$，求有多少个有序二元组(i,j)满足$(a_i \times a_j) \bmod P = a_k$，其中P为一给定质数。 求原根，转乘法为加法。上FFT。 ### BZOJ4503 两个串 兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。 这道题的关键在于'?'通配符的处理。**FFT也可以解决逻辑关系！**  类似的还有「PKUSC2018」神仙的游戏 ### 序列统计 **S中的0应去掉！**~~我好傻，第一次交，原根找错了~~ 给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。$M\le 8000$ 首先这个数据范围十分的鬼畜。我们冷静分析一下，模意义下，一些数的乘积等于定值$\to$求出原根，变成一些数的和等于定值，这样就有一些很好的性质了。 我们把集合变成生成函数，那么我们就是求$G^n$的一些位置系数和，下标$\mod m=\log X$。 所以我们要用正常快速幂的方法来写多项式快速幂，在做乘法的时候手动把下标取模即可。 ### 一类FFT的技巧-交换下标 AT2064 Many Easy Problems 这道题，我们得到了一个数组A[1...n]，我们要对$k=1...n$计算$\sum _i C^k_{A[i]}$ 单纯看这个形态，好像没什么可以优化的。但是，因为A数组的值域较小，我们可以**交换下标！** $\sum _i C^k_i\times cnt[i]$ 然后就可以FFT了 ### WD与积木 一个套路题，但是因为自己想的太复杂然后挂了。 对于集合划分类的问题，有以下两种套路： 1.集合是相同的。为了去重，我们需要枚举最后一个数放在哪（S2） 2.集合是不同的。我们枚举最后一个集合是什么。eg.$g(n)=\sum_i i!S_2(n,i)=\sum _i{n\choose i}g(n-i)$ ### FFT甚至可以解决矩阵匹配！ 见省选前作业：「THUPC2018」赛艇 / Citing ### 圆排列计数  如果是一个圆排列，方案数是多少？$(n-1)!$。如果是多个呢？我们需要做一个背包。那么直接Exp一下就行。 ### 【清华集训2016】如何优雅地求和 这道题的核心思想是发现，当$f(x)$为下降幂时很好求值，那么我们可以用牛顿表示法表示$f(x)$ 这道题给出的是点值，我们可以差分得到每次的系数：   ### FFT规律 把一个数组连着dft两遍，等于每个数乘n后reverse(a+1,a+n) 1 2 3 4 5 6 7 8 -> 8 64 56 48 40 32 24 16 原因的话把式子写开就可以了。 ----------------- ## 求一类无穷数列的卷积 $$[x^k]\frac{1}{(1-x)^n} \times \frac{1}{(1-x^2)^m}$$ 由于有$1-x^2=(1-x)\times (1+x)$ 乘上$\frac{(1+x)^n}{(1+x)^n}$ $$\frac{1}{(1-x)^n} \times \frac{1}{(1-x^2)^m}=(1+x)^n\times \frac{1}{(1-x^2)^{m+n}}$$ 然后就是有限项卷积无穷项了！！！对于第k次项，只有O(n)个来源！！！ 二项式展开，第二个生成函数展开，暴力卷积即可！！ -- by zky ## 一类分治FFT的写法 如果是自己卷自己的FFT，可能需要贡献的部分还没有计算完，怎么办？这时候可以把序列前边的一段拿过来，让它们没贡献的贡献了！ ## P4389 付公主的背包 完全背包的实质是生成函数的卷积，我们要求出$\prod \frac{1}{1-x^{v_i}}$的值，先取Ln，然后通过泰勒展开发现可以手动Ln。 ## 推导EGF的注意事项 如果递推式形如： $$F[n]=H[n]+\sum_{i\le n}{n\choose i}F[i]G[n-i]$$ **在转化为EGF时，记得前边H的每项系数也要除以$n!$** ## EOJ#136. K菌的游戏 求有多少棵外向树，使得下面这个博弈游戏先手必胜： 一开始根节点有一个棋子 每人每次可以找一个当前棋子所在节点的一个儿子，并把这个棋子移动过去 谁不能移动谁输  并不是任何时候，都把多重背包一样的东西写成$\exp$会更好。可能你发现式子会变成形如：$H=(x\exp H)'x+C$，然后就完全解不动了。我们尝试把所有的式子都用一个生成函数表示出来，然后分治NTT。 ### 长见识系列  ## 求和 如何求 $$\sum_i{a+i\choose a}x^i$$ 注意到${a+i\choose a}$相当于把i个球放入a+1个盒子，可以空的方案数。我们直接枚举每个盒子放多少，就变成了 $$1/(1-x)^{a+1}$$ ## 理解奇怪的指数在生成函数中的应用 $$eg. \sum_i{2i\choose i}x^i=(1-4x)^{-1/2}$$ 根据广义二项式定理， $$(1-4x)^{-1/2}=\sum_i{-1/2\choose i}(-4x)^i$$ 取$[x^n]$得： $$[x^n](1-4x)^{-1/2}=(-4)^n\times (-1/2)^{\underline{n}}/n!$$ 化简即可。 ## 【集训队作业2018】复读机 $$F=\sum_{d|i}x^i/i!=\sum_{i=0}^{d-1}e^{w_d^ix}$$ 其中$w_d$为d次单位根。 ## LOJ 6609 无意识的石子堆 拓宽了新思路。 首先把问题转化为左边n个点，要和右边m个点匹配，左边每个点要匹配2个，右边每个点匹配不多于2个。 我们枚举右边k个点匹配了2个点，那么右边点分为3部分，分别有$k,2n-2k,m-2n+k$ 我们可以把**匹配两个点的点拆成两个点**，这样左边和右边完美匹配的方案数是可以很方便的算出来的。 但是这样做会有重边，我们容斥去重。 $$f[k]=2^{-(n+k)}\sum_i(-1)^i{n\choose i}{k\choose i}i!2^i(2n-2i)!$$ 其中阶乘都是连边方案数，$2^i$是因为每个重边有两种方式（$(a,A),(b,B);(a,B),(b,A)$），前边的系数是因为我们此时把拆出来的两个点看成不同的，但其实没有顺序。 $$ans=\sum_k{m\choose k}{m-k\choose 2n-2k}f_k$$ n可以出到$10^6$，m可以出到$10^{18}$ ## CF947E 哇这道题好像很强的样子。 我们设$f_i$表示数字为i的概率，$f'_i$表示变换一次后为数字i的概率，那么显然有 $$f'_i=\sum_{i\le j} f_j/(j+1)$$ 用生成函数表示就是 $$F'=\sum_j f_j/(j+1)\sum_{i\le j}x^i$$ $$F'=\frac{1}{x-1}\sum_j (x^{j+1}-1)f_j/(j+1)$$ 接下来是激动人心的变形： $$(x^{j+1}-1)/(j+1)=\int_1^xt^j~dt$$ 代回去得到 $$F'=\frac{\int_1^xF(t)~dt}{x-1}$$ 这就很难受了，积分从1开始，分母是x-1.如果我们把函数错一位就很方便了：我们设$G(x)=F(x+1)$ $$G'=\frac{\int_0^xG(t)~dt}{x}$$ 用数列表示就是： $$g'_i=g_i/(i+1)$$ 变换m次也就是 $$g'_i=g_i/(i+1)^m$$ 把F和G相互转换是简单的。 ### EGF的DP式子一般不要去想$f_i\to f_{i+1}$的递推，直接去把计数的对象拆成几个部分，然后把它们拼起来！