删本地文件的时候瞟了一眼内容 ... 这篇好像忘记发布了?
给定 \(n,k\), 求出
\[\textit{ans}=\sum_{i=0}^n\binom{n}{i}i^k\bmod(10^9+7). \]\(k\le5\times10^3\), \(n\le10^9\).
\[\textit{ans} = \sum_{i=0}^n\binom{n}{i}k![x^k]e^{ix}= k^n. \]
EI 提供了一种规避高次幂计算的方法. 其本质是构造常数项为 \(0\) 的多项式, 再利用欲提取的系数位置 \(k\ll n\) 来降低幂次. 这里, 令 \(F(z)=(z+1)^n\), 并设 \(\mathscr F(z+1)=F(z+1)\bmod z^{k+1}\). 我们最终向 \(F(z+1)\) 代入的是 \(z=e^x-1\), 由于 \([x^0](e^x-1)=0\), 所以可以对 \(F(z+1)\) 进行截断操作, 将目标转化为求 \(\mathscr F(z+1)\).
考虑 \(F(z+1)\) 的 ODE 与 \(\mathscr F(z+1)\) 的 ODE 的关系:
\[(2+z)F'(z+1)-nF(z+1)=0\\ \begin{aligned} \Rightarrow (2+z)\mathscr F'(z+1)-n\mathscr F(z+1) &= -2z^k[z^k]F'(z+1)\\ &= -2n\binom{n-1}{k}2^{n-1-k}z^k\\ &= (k-n)\binom{n}{k}2^{n-k}z^k. \end{aligned} \]目标是求 \(\mathscr F(z+1)\) 的各项系数. 令 \(t=z+1\), 左右提取 \([t^i]\) 得
\[(i+1)[t^{i+1}]\mathscr F(t)+i[t^i]\mathscr F(t)-n[t^i]\mathscr F(t)=(k-n)\binom{n}{k}2^{n-k}\binom{k}{i}(-1)^{k-i}\\ \Rightarrow [t^{i+1}]\mathscr F(t)=\frac{1}{i+1}\left((k-n)\binom{n}{k}2^{n-k}\binom{k}{i}(-1)^{k-i}+(n-i)[t^i]\mathscr F(t)\right). \]不过还需要求出 \([t^0]\mathscr F(t)\). 注意 \([z^i]\mathscr F(t)\) 非常好求, 拿它来表示 \([t^0]\mathscr F(t)\):
\[\begin{aligned}[] [t^0]\mathscr F(t) &= \sum_{i=0}^k[z^i]\mathscr F(t)\cdot(-1)^i\\ &= \sum_{i=0}^k\binom{n}{i}2^{n-i}(-1)^i. \end{aligned} \]最终
\[\textit{ans}=k![x^k]\mathscr F(e^x)=\sum_{i=0}^ki^k[t^i]\mathscr F(t). \]可以做到 \(\mathcal O(k)\).
喷一下洛谷日报, 跳过转化性的步骤留下初等的化简步骤, 真的很 confusing 呐.
给定 \(n,k\), 求出
\[\textit{ans}=\sum_{i=0}^nf_ii^k\bmod(10^9+7), \]其中 \(f\) 为 Fibonacci 数列, \(f_0=f_1=1\).
\(n\le10^{17}\), \(k\le40\).
和上一题差不多, 令 \(F(x)\) 为 Fibonacci 数列的 OGF\(\bmod x^{n+1}\) 所得多项式, 则
\[\textit{ans}=k![x^k]F(e^x). \]分离 \(e^x\) 的常数项 \(e^x=(e^x-1)+1\), 则进行截取
\[\mathscr F(z+1)=F(z+1)\bmod z^{k+1}. \]对于 \(F(z)\), 有
\[F(z)=\frac{1-f_{n+1}z^{n+1}-f_nz^{n+2}}{1-z-z^2}. \]设 \(P(z)=1-f_{n+1}z^{n+1}-f_nz^{n+2}\), 于是
\[\mathscr F(z+1)=-\frac{P(z+1)}{1+3z+z^2}\bmod z^{k+1}. \]问题是我们啥也不会求 ... 从 \(P(z+1)\) 开始, 设 \(\mathscr P(z+1)=P(z+1)\bmod z^{k+1}\). 注意截断 \(P(z+1)\) 的主要矛盾不过是截断 \(G_n(z+1)=(z+1)^n\). 而这玩意儿可以和刚才一样建立 ODE 并进行扰动求出. 具体地:
\[(z+1)G_n'(z+1)-nG_n(z+1)=0\\ \begin{aligned} \Rightarrow (z+1)\mathscr G_n'(z+1)-n\mathscr G_n(z+1) &= -nz^k[z^k](z+1)^{n-1}\\ &= (k-n)\binom{n}{k}z^k. \end{aligned} \]提取系数, 据此可以递推求出 \(\mathscr G_n(z+1)\) 的系数, 继而求出 \(\mathscr P(z+1)\).
此后, 写出 \(F\) 的线性递推:
\[F(z+1)=3zF(z+1)+z^2F(z+1)-P(z+1)\\ \Rightarrow [z^i]F(z+1)=-3[z^{i-1}]F(z+1)-[z^{i-2}]F(z+1)-[z^i]P(z+1). \]考虑取模在 \(\mathscr F\) 上带来的扰动:
\[\begin{aligned}[] [z^i]\mathscr F(z+1) &= -3[z^{i-1}]\mathscr F(z+1)-[z^{i-2}]\mathscr F(z+1)-[z^i]\mathscr P(z+1)\\ &+ [i=k+1]\cdot(3[z^{i-1}]\mathscr F(z+1)+[z^{i-2}]\mathscr F(z+1))\\ &+ [i=k+2]\cdot[z^{i-2}]\mathscr F(z+1). \end{aligned} \]注意小细节, \(\mathscr F(z+1)=F(z+1)\bmod z^{k+1}\) 是定义, 我们需要在递推上作修补让递推符合这一定义, 而非直接将 \(z^{k+1}\) 等项忽略.
令 \(a=3[z^k]\mathscr F(z+1)+[z^{k-1}]\mathscr F(z+1)\), \(b=[z^k]\mathscr F(z+1)\), 那么
\[\mathscr F(z+1)=-\frac{\mathscr P(z+1)-az^{k+1}-bz^{k+2}}{1+3z+z^2}\\ \Rightarrow \mathscr F(z)=\frac{\mathscr P(z)-a(z-1)^{k+1}-b(z-1)^{k+2}}{1-z-z^2}. \]还是线性递推. 将其求出再同上题一样代回即可求出答案. 复杂度 \(\mathcal O(k)\).
标签：Set,mathscr,Sum,aligned,sum,textit,binom,例题,bmod From： https://www.cnblogs.com/rainybunny/p/16789412.html