考试时多项式推错惨遭爆零
首先，这道题很明显式子是一个二项卷积，考虑 EGF
不妨设
\[ f=\sum_np^n\lfloor\frac{n}{k}\rfloor\frac{x^n}{n!} \] 则答案为
\[ [x^n]e^x\times f \]
现在考虑 \(f\) 如何求出
由于 EGF 的移位和指标下放很好实现，所以考虑多项式
\[ \hat{f}_n=\sum_i[n|i]\frac{x^i}{i!} \]
显然 \(\hat{f}_2\) 很好求出，即为
\[ \hat{f}_2=\frac{e^x+e^{-x}}{2} \]
这也启发我们 \(\hat{f}_n\) 可以用若干个形如 \(e^{kx}\) 组合出
于是我们想到了单位根，即
\[ w_n^{in}=1 \]
对于 \(w_n^i\) 而言，有
\[ \frac{1}{n}\sum_{k=0}^{n-1}w_n^{ik}=[i=0] \]
那么可以得出
\[ \hat{f_n}=\frac{1}{n}\sum_{i=0}^{n-1}e^{w_n^ix} \]
同时根据 EGF 的性质
\[ \frac{\partial\hat{f}_n}{\partial x^k}=\sum_i[n|(i+k)]\frac{x^i}{i!} \]
乘上 \(\frac{x}{n}\) 就有
\[ \frac{x}{n}\times\frac{\partial\hat{f}_n}{\partial x^k}=\sum_i[n|(i+k-1)]\frac{i}{n}\frac{x^i}{i!} \]
结合之前就有
\[ \frac{x}{n}\times\frac{\partial\hat{f}_n}{\partial x^k}+\frac{k-1}{n}\times\frac{\partial\hat{f}_n}{\partial x^{k-1}}=\sum_i[n|(i+k-1)]\lceil\frac{i}{n}\rceil\frac{x^i}{i!} \]
所以当 \(k\ge2\) 时
\[ \frac{x}{n}\times\frac{\partial\hat{f}_n}{\partial x^k}+\frac{k-1}{n}\times\frac{\partial\hat{f}_n}{\partial x^{k-1}}-\frac{\partial\hat{f}_n}{\partial x^{k-1}}=\sum_i[n|(i+k-1)]\lfloor\frac{i}{n}\rfloor\frac{x^i}{i!} \]
综上讨论
\[ f=\sum_{k=1}^n\frac{x}{n}\times\frac{\partial\hat{f_n}}{\partial x^k}+\sum_{k=1}^n\frac{k-1}{n}\times\frac{\partial\hat{f_n}}{\partial x^{k-1}}-\sum_{k=2}^n\frac{\partial\hat{f_n}}{\partial x^{k-1}} \]
而对于 \(\frac{\partial\hat{f_n}}{\partial x^k}\) 有
\[ \frac{\partial\hat{f_n}}{\partial x^k}=\frac{1}{n}\sum_{i=0}^{n-1}w_n^{ik}e^{w_n^ix} \]
根据交换求和式的技巧我们可以把式子简化为只有一个和式而无嵌套情况，以中间的和式为例
\[ \sum_{k=1}^n\frac{k-1}{n}\times\frac{\partial\hat{f_n}}{\partial x^{k-1}}=\frac{1}{n^2}\sum_{i=0}^{n-1}\sum_{k=1}^n(k-1)\times w_n^{i(k-1)}e^{w_n^ix} \]
根据
\[ \sum_{i=1}^nix^{i-1}=\frac{nx^{n+1}-nx^n-x^n+1}{(x-1)^2} \]
上面的式子可以化简为
\[ \sum_{i=1}^{n-1}\frac{1}{n\times(w_n^i-1)}e^{w_n^ix}+\frac{n-1}{2\times n}e^x \]
其他同理
最后的问题只有单位根怎么求了，由于 \(998244353\) 为 NTT 质数，所以
\(2^k\) 的单位根就可以表示为 \(3^{\frac{P-1}{2^k}}\)
1 |
|