====== 多项式应用 ====== ===== 习题一 ===== [[https://www.luogu.com.cn/problem/P3702|洛谷p3702]] ==== 题意 ==== 询问有多少序列满足下列条件： - 序列长度等于 $n$ - 序列由不超过 $m$ 的正整数构成且至少含有一个素数 - 序列所有数之和是 $p$ 的倍数 ==== 题解 ==== 考虑容斥，于是答案为由不超过 $m$ 的正整数构成的序列数减去不超过 $m$ 的合数构成的序列数。不超过 $m$ 且模 $p$ 为 $i$ 的正整数个数，而利用线性筛可以计算出不超过 $m$ 且模 $p$ 为 $i$ 的合数个数。设 $\text{dp}(i,j)$ 表示长度为 $i$ 且和模 $p$ 为 $j$ 的序列数，发现可以利用倍增 $+$ $\text{NTT}$ 转移。时间复杂度 $O(m+p\log n\log p)$。本题 $p\le 100$ 且模数为合数，所以考虑直接暴力转移，时间复杂度 $O(m+p^2\log n)$。


const int MAXM=2e7+5,MAXP=105,Mod=20170408;
int prime[MAXM],p_cnt,p;
bool vis[MAXM];
void get_prime(int n){
	vis[1]=true;
	_rep(i,2,n){
		if(!vis[i])prime[p_cnt++]=i;
		for(int j=0;i*prime[j]<=n&&j=0;i--){
		if(n&(1<



===== 习题二（字符串匹配） =====

[[https://www.luogu.com.cn/problem/P4173|洛谷p4173]]

==== 题意 ====

给定只包含小写字母和通配符的字符串 $A,B$。其中 $A$ 为模板串，$|A|=m,|B|=n$。询问所有匹配位置。

==== 题解 ====

构成字符集到数值的映射

$$
f(x)=
\begin{cases}
x-a &x= a\sim z\\
0 &x=*
\end{cases}
$$

令 $c_i=\sum_{j=0}^{m-1}\left(f(a_j)-f(b_{i-m+1+j})\right)^2f(a_j)f(b_{i-m+1+j})$。

于是 $B$ 中第 $i$ 个字符结尾的长度为 $m$ 的字符串与 $A$ 匹配当且仅当 $c_i=0$。令 $t_i=a_{m-1-i}$，有

$$\sum_{x+y=i}\left(f(t_x)-f(b_y)\right)^2f(t_x)f(b_y)=\sum_{x+y=i}f(t_x)^3f(b_y)+\sum_{x+y=i}f(t_x)f(b_y)^3-2\sum_{x+y=i}f(t_x)^2f(b_y)^2$$

于是直接 $\text{FFT}$ 即可，时间复杂度 $O(n\log n)$。



const int MAXN=3e5+5;
const double pi=acos(-1.0);
struct complex{
	double x,y;
	complex(double x=0.0,double y=0.0):x(x),y(y){}
	complex operator + (const complex &b){
		return complex(x+b.x,y+b.y);
	}
	complex operator - (const complex &b){
		return complex(x-b.x,y-b.y);
	}
	complex operator * (const complex &b){
		return complex(x*b.x-y*b.y,x*b.y+y*b.x);
	}
	complex operator * (const int &b){
		return complex(x*b,y*b);
	}
}w[32][2];
int rev[MAXN<<2];
int build(int k){
	int n,pos=0;
	while((1<>1]>>1)|((i&1)<<(pos-1));
	for(int i=1,t=0;i


===== 习题三（差分与前缀和） =====

[[https://www.luogu.com.cn/problem/P5488|洛谷p5488]]

==== 题意 ====

给定一个长度为 $n$ 的序列 $a$，求 $a$ 的 $k$ 阶差分或前缀和。

==== 题解 ====

设序列的生成函数为 $F(x)=\sum_{i=0}^{n-1} a_ix^i$，则 $k$ 阶差分等价于

$$
F(x)(1-x)^k=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i{i\choose k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {k^{\underline i}}{i!}
$$

而 $k$ 阶前缀和等价于

$$
F(x)(1+x+x^2+x^3+\cdots)^k=F(x)(1-x)^{-k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {(-k)^{\underline i}}{i!}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}\frac {k^{\overline i}}{i!}
$$

直接 $O(n)$ 递推出系数然后 $\text{NTT}$ 卷积即可。时间复杂度 $O(n\log n)$。



const int MAXN=1e5+5,Mod=1004535809;
int quick_pow(int a,int b){
	int t=1;
	while(b){
		if(b&1)
		t=1LL*t*a%Mod;
		a=1LL*a*a%Mod;
		b>>=1;
	}
	return t%Mod;
}
namespace Poly{
	const int G=3;
	int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30];
	void init(){
		int lg2=0,*pos=Pool,n,w;
		while((1<>=1;
		}
	}
	int build(int k){
		int n,pos=0;
		while((1<>1]>>1)|((i&1)<<(pos-1));
		return n;
	}
	void NTT(int *f,int n,bool type){
		_for(i,0,n)if(i


===== 习题四（矩阵卷积） =====

==== 题意 ====

考虑快速计算序列 $\{C\}$，其中 $A_i,B_i$ 均为 $w\times w$ 矩阵

$$
C_i=\sum_{j=0}^i A_jB_{i-j}(0\le i\le n)
$$

==== 题解 ====

不难发现 $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$，于是 $c_{ij}$ 可以拆分成 $w$ 个卷积。

考虑 $O\left(w^2n\log n\right)$ 预处理出 $\{a_{ij}\}$ 和 $\{b_{ij}\}$ 的 $\text{DFT}$ 结果。然后通过  $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$ 可以 $O\left(w^3n\right)$ 计算每个 $\{c_{ij}\}$ 的 $\text{DFT}$ 结果。

最后对每个 $\{c_{ij}\}$ 做 $\text{IDFT}$，总时间复杂度 $O\left(w^2n\log n+w^3n\right)$。