[思维+FFT]BZOJ4259【残缺的字符串】题解
题目概述有两个串 $A,B$ ，有些位置是通配符，求 $A$ 可以在 $B$ 的哪些位置匹配。解题报告早就听说了这题，今天来填坑。判断两个字符串相等可以用式子：$\sum_{i=0}^{len}...
[生成函数+FFT]计蒜客NAIPC2016E【K-Inversions】题解
题目概述有一个AB字符串，问间距为 $k$ 的BA对有多少，其中 $k\in[1,n-1]$ 。解题报告emm……应该算是生成函数吧？令A的位置的权值为下标，B的位置的权值为下标的相反数，那么只...
NTT
快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。然而这货和FFT基本上一样，就是求 \(A(x)B(x)\) ，只不过系数要对 \(p\)...
[拆系数FFT]洛谷4245【任意模数NTT】题解
题目概述求 \(A(x)B(x)\) ，系数对任意模数 \(p\) 取模。解题报告任意模数NTT好像需要三模数NTT搞。然而我不会NTT……所以我来愉快的讲一波任意模数FFT（雾）。其实洛谷里p...