单位根反演
\[ \frac{1}{k}\sum_{i=0}^{k-1}\omega_k^{in}=[k|n] \]
所以
\[ \begin{equation} \begin{split} \sum_{i=1}^{n}a_i[k|i]&=\frac{1}{k}\sum_{i=1}^{n}a_i\sum_{j=0}^{k-1}\omega_k^{ji}\\ &=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=1}^{n}a_i\omega_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}\)
半平面交
大佬