单位根反演
[frac{1}{k}sum_{i=0}^{k-1}omega_k^{in}=[k|n]
]
所以
[egin{equation}
egin{split}
sum_{i=1}^{n}a_i[k|i]&=frac{1}{k}sum_{i=1}^{n}a_isum_{j=0}^{k-1}omega_k^{ji}\
&=frac{1}{k}sum_{j=0}^{k-1}sum_{i=1}^{n}a_iomega_k^{ji}\
&=frac{1}{k}sum_{j=0}^{k-1}f(omega_k^{j})
end{split}
end{equation}
]
这样可以使得复杂度从(n)倾向(k)
在模(998244353)的意义下，(omega_k^{1}=g^{frac{P-1}{k}})
概率生成函数
定义
我们定义一个形式幂级数(A(x))，称它为离散随机变量(X)的概率生成函数
其中(A(x))的每一项系数(a_i)，都有(a_i=P(X=i))
性质
(A(1)=1)
(A'(x)=E(X)=sum iP(X=i)x^{i-1})