载谭 Binomial Sums 学习笔记
forest114514 · · 算法·理论
载谭 Binomial Sums 学习笔记
小 F 发誓 NOIP 不退役就一定学懂的东西，今天填坑。
求的是什么？
对于 D-Finite 的 GF
F(x) 和另一个普通 GFG(x) 如果对k\in [0,n] 知道b_k=\sum\limits_{j=0}^{n}a_j[x^j]G(x)^k ，就能在O(n) 时间算\sum\limits_{j=0}^{n}a_j[x^j]F(G(x)) 。具体地，求出
\mathbb{F}(x),\mathbb{F}(x+c)=F(x+c)\bmod x^{n+1} ，f_i=[x^n]\mathbb{F}(x) ，则ans=\sum\limits_{i\geq 0}f_ib_i
感觉比较抽象。简单证明：
\begin{aligned} F(G(x))&=\sum\limits_{i\geq 0} \frac{F^{(i)}(c)}{i!} (G(x)-c)^i\\ &\equiv\sum\limits_{i=0}^{n} \frac{F^{(i)}(c)}{i!} (G(x)-c)^i\pmod x^{n+1}\\ &\equiv\sum\limits_{i=0}^{n} \frac{ F^{(i)}(c)}{i!} (G(x)-c)^i\pmod x^{n+1}\\ \end{aligned} 所以有：
F((G(x)-c)+c)\equiv \mathbb F((G(x)-c)+c)\bmod {(G(x)-c)^{n+1}}=\mathbb F((G(x)-c)+c) 。注意到
G(x)-c 没有常数项。
怎么求？
考虑 ODE：
然后用你擅长的提取系数整式递推就行了，难度在于这个和构造
习题（不断更新中）：
-
bell 数
注意到
F(x)=e^{x-1},G(x)=e^x,ans=[x^n]F(G(x)) 。直接推式子：
\begin{aligned}\ [\frac{x^n}{n!}]e^{e^x-1}&=[\frac{x^n}{n!}]\sum\limits_{i=0}^{n}\frac{1}{i!}(e^x-1)^n\\ &=[\frac{x^n}{n!}]\sum\limits_{i=0}^{n}\frac{1}{i!}\sum\limits_{j=0}^{i}\binom{i}{j}(-1)^{j}e^{(i-j)x}\\ &=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}\frac{(-1)^{j}}{j!}\frac{(i-j)^n}{(i-j)!}\\ &=\sum\limits_{i=0}^{n}\frac{i^n}{i!}\sum\limits_{j=0}^{n-i}\frac{(-1)^j}{j!} \end{aligned} 使用 ODE：
\begin{aligned} F(x+1)-F'(x+1)&=0\\ \mathbb{F}(x+1)-\mathbb{F}'(x+1)&=\frac{x^n}{n!}\\ \mathbb{F}(x)-\mathbb{F}'(x)&=\frac{(x-1)^n}{n!}=\frac{1}{n!}\sum\limits_{i=0} ^{n}\binom{n}{i}(-1)^{n-i}x^{i}\\ f_{k}-f_{k+1}&=\frac{(-1)^{n-k}}{(n-k)!} \end{aligned} -
线性插值
我们已知 $b_X=\sum\limits_{i=0}^{n}a_iX^i=\sum\limits_{i=0}^{n}a_i[\frac{x^i}{i!}]e^{iX}$，求 $\sum\limits_{i=0}^{n}a_ik^i=\sum\limits_{i=0}^{n}a_i[\frac{x^i}{i!}]e^{k}$，所以 $F(x)=x^k,G(x)=e^x$。 使用 ODE： $$ \begin{aligned} kF(x+1)-(x+1)F'(x+1)&=0\\ k\mathbb F(x+1)-(x+1)\mathbb F'(x+1)&=(k-n)\binom{k}{n}x^n\\ k\mathbb F(x)-x\mathbb F'(x)&=(k-n)\binom{k}{n}(x-1)^n\\ kf_i-if_i&=(k-n)\binom{k}{n}\binom{n}{i}(-1)^{n-i} \end{aligned} $$ -
P5907 数列求和加强版 / SPOJ MOON4
不难构造出 $G(x)=ae^x,b_X=[x^n]G(x)^i,F(x)=\frac{1-x^{k+1}}{1-x} 小 F 认为一阶线性 ODE 都是齐次的，邮电部诗人，记住是
\frac{dF(x)}{dx}=P(x)F(x)+Q(x) \begin{aligned} F(x)+(x-1)F'(x)&=(x^{k+1}-1)'=(x^{k+1})'\\ F(x+a)+(x+a-1)F'(x+a)&=\left[(x+a)^{k+1}\right]'\\ \mathbb F(x+a)+(x+a-1)\mathbb F'(x+a)&=\left[\sum\limits_{i=0}^{n}\binom{k+1}{i}a^{k+1-i}x^i\right]'+(n+1)x^n\sum\limits_{i=n}^{k}\binom{i}{n}a^{i-n}\\ \mathbb F(x)+(x-1)\mathbb F'(x)&=\left[\sum\limits_{i=0}^{n}\binom{k+1}{i}a^{k+1-i}(x-a)^i\right]'+(n+1)(x-a)^n\sum\limits_{i=n}^{k}\binom{i}{n}a^{i-n}\\ \mathbb F(x)+(x-1)\mathbb F'(x)&=\left[\sum\limits_{i=0}^{n}\binom{k+1}{i}a^{k+1-i}\sum\limits_{j=0}^{i}\binom{i}{j}(-a)^{i-j}x^j\right]'+(n+1)\sum\limits_{i=n}^{k}\binom{i}{n}a^{i-n}\sum\limits_{j=0}^{n}\binom{n}{j}(-a)^{n-j}x^j\\ \end{aligned} 好了现在有几个问题需要解决：
-
$$ \begin{aligned} &\sum\limits_{i=0}^{n}\binom{k+1}{i}a^{k+1-i}\sum\limits_{j=0}^{i}\binom{i}{j}(-a)^{i-j}x^j\\ =&\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}\binom{k+1}{i}\binom{i}{j}(-1)^{i-j}a^{k+1-j}x^j\\ =&\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}\binom{k+1}{j}\binom{k-j}{i-j}(-1)^{i-j}a^{k+1-j}x^j\\ =&\sum\limits_{j=0}^{n}\binom{k+1}{j}a^{k-j}x^j\sum\limits_{d=0}^{n-j}\binom{k+1-j}{d}(-1)^{d}\\ &注意到\\ &\sum\limits_{d=0}^{n-j}\binom{k+1-j}{d}(-1)^{d}\\ =&\sum\limits_{d=0}^{n-j}\left[\binom{k-j}{d}+\binom{k-j}{d-1}\right](-1)^{d}\\ =&\sum\limits_{d=0}^{n-j}\binom{k-j}{d}(-1)^{d}-\sum\limits_{d=0}^{n-j-1}\binom{k-j}{d}(-1)^{d}\\ =&\binom{k-j}{n-j}(-1)^{n-j}\\ &所以原式等于 \sum\limits_{j=0}^{n}(-1)^{n-j}\binom{k+1}{j}\binom{k-j}{n-j}a^{k-j}x^j\\ &显然导数就是\sum\limits_{j=1}^{n}(-1)^{n-j}\binom{k+1}{j}\binom{k-j}{n-j}a^{k-j}jx^{j-1} \end{aligned} $$ -
$$ \begin{aligned} T(0)&=\sum\limits_{i=1}^{k}a^i=\frac{a^{k+1}-1}{a-1} \\ T(n)&=\sum\limits_{i=n}^{k}\binom{i}{n}a^{i-n}\\ &=\sum\limits_{i=n}^{k}\left[\binom{i-1}{n}+\binom{i-1}{n-1}\right]a^{i-n}\\ &=a\sum\limits_{i-1=n}^{k-1}\binom{i-1}{n}a^{i-1-n}+\sum\limits_{i-1=n-1}^{k-1} \binom{i-1}{n-1}a^{(i-1)-(n-1)}\\ &=a(T(n)-\binom{k}{n}a^{k-n})+T(n-1)-\binom{k}{n-1}a^{k-n+1}\\ &=aT(n)+T(n-1)-\binom{k+1}{n}a^{k-n+1} \end{aligned} $$ 可以直接 $O(n)$ 递推，$(k+1)^{\underline{i}}$ 是好求的。
最后直接递推的时候从低往高递推不是很方便，但是我们的
\mathbb F 既然是F 的截断[x^n]\mathbb F 是容易求的，反着推简单很多。 -
-
“Binomial Sum” CF932E
可以构造出 $F(x)=(1+x)^{k},G(x)=e^x,b_X=[\frac{x^n}{n!}]G(x)^X,ans=[\frac{x^n}{n!}]F(G(x))$。 直接快进到 ODE： $$ \begin{aligned} kF(x)-(x+1)F'(x)&=0\\ kF(x+1)-(x+2)F(x+1)&=0\\ k\mathbb F(x+1)-(x+2)\mathbb F'(x+1)&=(k-n)\binom{k}{n}2^{k-n}x^n\\ k\mathbb F(x)-(x+1)\mathbb F'(x)&=(k-n)\binom{k}{n}2^{k-n}(x-1)^n\\ k\mathbb F(x)-(x+1)\mathbb F'(x)&=(k-n)\binom{k}{n}2^{k-n}\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^{n-i}x^i \end{aligned} $$ -
CF392C Yet Another Number Sequence
做法一：
原题可以写成
\frac{1}{\sqrt{5}}\sum\limits_{i=0}^{n}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n]i^k ，在\sqrt 5 有二次剩余的时候就和 P5907 一模一样了，那个题的做法可以看我的题解。但是
\sqrt 5 在本题没有二次剩余，考虑扩域即可，可以做到O(k+\log n) ，考虑如果\log n 很大是没法接受的数的话你扩域的数(a+\sqrt 5b)^i 满足(a+\sqrt 5b)^{p^2}=a+\sqrt 5b ，可以做到O(k+\log p) 。做法二：
其实还是可以根据斐波那契数列的 GF 直接截断然后得到 ODE 来做的，只是麻烦一点。
截断可以得到：
(x^2+x-1)F(x)=(fib_{n-1}+fib_{n})x^{n+1}+fibx^{n+2}-1 设右边那个为
P(x) ，两边求导可以得到 ODE 为：(2x+1)F(x)+(x^2+x-1)F'(x)=P'(x) 带入
x+G(0)=x+1 得到：(2x+3)F(x+1)+(x^2+3x+1)F'(x+1)=P'(x+1) 设
\mathbb F(x)=F(x)\bmod x^{k+1},\mathbb P(x)=P(x)\bmod x^{k+1} ，就能截断得到：(2x+3)\mathbb F(x+1)+(x^2+3x+1)\mathbb F'(x+1)=\mathbb P'(x+1)+Ax^k+Bx^{k+1} 其中
A=(n+1)[x^{k-1}]F(x+1)+(3n+3)[x^k]F(x+1),B=(n+2)[x^k]F(x+1) ，对于F(x+1) 的某一项的系数其实就是求\sum\limits_{i=n}^{k}fib_i\binom{i}{n} ，直接扩域后就和 P5907 的某个部分一样的了，可以看我的题解。后面带回
x 就能得到：(2x+1)\mathbb F(x)+(x^2+x-1)\mathbb F'(x)=[\mathbb P(x+1)\circ (x-1)]'+A(x-1)^n+B(x-1)^{n+1} -
P5401 [CTS2019] 珍珠
不关心珍珠的具体分布，只关心每种珍珠的数量，最后乘上多重组合数，所以直接用 EGF。
最后对数就是
\sum\limits_{i=1}^{D}\lfloor\frac{cnt}{2}\rfloor\geq m ，就是出现次数奇数次的小于等于n-2m ，不妨设k=n-2m ，在D\leq k 的时候怎么都合法，在k<0 的时候怎么都不合法，特判掉，此时剩下k<D 。然后就是枚举选了奇数偶数次的方案数：
[\frac{x^n}{n!}] \sum\limits_{i=0}^{k}\binom{D}{i}(\frac{e^x-e^{-x}}{2})^i(\frac{e^x+e^{-x}}{2})^{D-i}=\frac{1}{2^D}[\frac{x^n}{n!}] \sum\limits_{i=0}^{k}\binom{D}{i}(e^x-e^{-x})^i(e^x+e^{-x})^{D-i} 设
G(x)=e^x,F(x)= \sum\limits_{i=0}^{k}\binom{D}{i}(x-x^{-1 })^i(x+x^{-1})^{D-i} 。但是你遇到了有负数次项的F(x) ，这不好，我们不会截断形式 Laurent 级数，我们考虑换成没有负数次幂的形式，而且e^x 上带负数也不影响的，所以可以写成\frac{1}{2^D}[\frac{x^n}{n!}] e^{-Dx}\sum\limits_{i=0}^{k}\binom{D}{i}(e^{2x}-1)^i(e^{2x}+1)^{D-i} 。这下设
G(x)=e^{2x},F(x)= \sum\limits_{i=0}^{k}\binom{D}{i}(x-1)^i(x+1)^{D-i} ，我们要求\sum\limits_{i=0}^{n}(-D)^{n-i}[\frac{x^{i}}{i!}]F(G(x)) ，这样好做一点。回忆 binomial sums 的条件，先求
b_X=\sum\limits_{i=0}^{n}(-D)^{n-i}[\frac{x^i}{i!}](e^{2x})^X=\sum\limits_{i=0}^{n}(-D)^{n-i}(2X)^i=\frac{(-D)^n((\frac{2X}{-D})^{n+1}-1)}{\frac{2X}{-D}-1}=\frac{(2X)^{n+1}-(-D)^{n+1}}{2X+D} X^{n} 可以直接线性筛，底下的可以求线性逆元。然后求
F(x) 截断后的系数，首先我们需要 ODE，但似乎F(x) 有一点复杂，先求导试试。\begin{aligned} F(x)'&=\sum\limits_{i=0}^{k}\binom{D}{i}(i(x-1)^{i-1}(x+1)^{D-i}+(D-i)(x-1)^{i}(x+1)^{D-i-1})\\ &=D\sum\limits_{i=0}^{k}\binom{D-1}{i-1}(x-1)^{i-1}(x+1)^{D-1-(i-1)}+D\sum\limits_{i=0}^{k}\binom{D-1}{i}(x-1)^i(x+1)^{D-1-i}\\ &=D\sum\limits_{i=0}^{k}\binom{D-1}{i-1}(x-1)^{i-1}(x+1)^{D-1-(i-1)}+D\sum\limits_{i=0}^{k}\binom{D-1}{i}(x-1)^i(x+1)^{D-1-i}\\ \end{aligned} 这里的
\binom{D-1}{i-1} 和\binom{D-1}{i} 提示我们拆组合数，考虑把F(x) 拆了。\begin{aligned} F(x)&=\sum\limits_{i=0}^{k}\binom{D}{i}(x-1)^{i}(x+1)^{D-i}\\ &=\sum\limits_{i=0}^{k}\binom{D-1}{i}(x-1)^{i}(x+1)^{D-i}+\sum\limits_{i=0}^{k}\binom{D-1}{i-1}(x-1)^{i}(x+1)^{D-i}\\ &=(x+1)\sum\limits_{i=0}^{k}\binom{D-1}{i}(x-1)^{i}(x+1)^{D-1-i}+(x-1)\sum\limits_{i=0}^{k}\binom{D-1}{i-1}(x-1)^{i-1}(x+1)^{D-1-(i-1)}\\ &=\frac{x}{D}F'(x)+\sum\limits_{i=0}^{k}\binom{D-1}{i}(x-1)^{i}(x+1)^{D-1-i}-\sum\limits_{i=0}^{k}\binom{D-1}{i-1}(x-1)^{i-1}(x+1)^{D-1-(i-1)}\\ &=\frac{x}{D}F'(x)+\binom{D-1}{k}(x-1)^{k}(x+1)^{D-1-k} \end{aligned} 所以得到的 ODE 就是，可以把右边设成
P(x) ：DF(x)-xF(x)'=D\binom{D-1}{k}(x-1)^{k}(x+1)^{D-1-k}=P(x) 然后我们有个好消息，
F(x) 和P(x) 的次数都不超过D ，不用截断，而且左边提取系数发现其实是(D-i)f_i=[x^i]P(x) ，甚至不用整式递推，直接求右边的系数就行了，考虑如何提取P(x) 的系数，一般的我们要提取Q(x)=(x+1)^a(x-1)^b 的系数，这个 feelcle 讲过，直接求导继续 ODE 转整式递推。\begin{aligned} Q(x)'&=b(x+1)^a(x-1)^{b-1}+a(x+1)^{a-1}(x-1)^b\\ Q(x)'&=\frac{b}{x-1}Q(x)+\frac{a}{x+1}Q(x)\\ (x^2-1)Q(x)'&=((a+b)x+b-a)Q(x)\\ (n-1)q_{n-1}-(n+1)q_{n+1}&=(a+b)q_{n-1}+(b-a)q_{n}\\ q_{n+1}&=(b-a)q_{n}+(a+b-n+1)q_{n-1} \end{aligned} 最后答案就是
\sum\limits_{i=0}^{D}f_{i}b_{i} ，时间复杂度O(D\log_{D}n)=O(D) 。 -
P4091 [HEOI2016/TJOI2016] 求和
第二类斯特林数有行和列两种切入法，行就是经典式子 ${i\brace j}j!=\sum\limits_{k=0}^{j}(-1)^{j-k}\binom{j}{k}k^i$，这个能导出一个 $O(n\log n)$ 的 NTT 做法，但是优化不了一点。 列的话就是 ${i\brace j}j!=[\frac{x^i}{i!}](e^x-1)^j$，又是我们喜欢的 $e^x-1$，考虑把这个代回去： $$ \begin{aligned} &\sum\limits_{i=0}^{n}[x^i]\sum\limits_{j=0}^{i}2^j(e^x-1)^{j}\\ =&\sum\limits_{i=0}^{n}[x^i]\sum\limits_{j=0}^{n}2^j(e^x-1)^{j} \end{aligned} $$ 还是发现 $G(x)=e^x,F(x)=\sum\limits_{j=0}^{n}2^j(x-1)^{j}$，求的是 $\sum\limits_{i=0}^{n}[\frac{x^i}{i!}]F(G(x))$。 先考虑求 $b_X=\sum\limits_{i=0}^{n}[\frac{x^i}{i!}]G(x)^{X}=\sum\limits_{i=0}^{n}[\frac{x^i}{i!}]e^{Xx}=\sum\limits_{i=0}^{n}X^i$，对 $X=1$ 容易的，否则就是 $\frac{X^{n+1}-1}{X-1}$，直接筛 $i^{n+1}$，线性求一下逆元就行了。 然后考虑怎么求 $F(x)$ 的系数，因为 $F(x)$ 的最高次项系数都是 $n$ 所以不用截断，直接大力推，比 ODE 容易点。 $$ \begin{aligned} F(x)&=\sum\limits_{i=0}^{n}2^i\sum\limits_{j=0}^{i}\binom{i}{j}(-1)^{i-j}x^j\\ &=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n}\binom{i}{j}(-2)^{i-j}2^jx^{j}\\ &=\sum\limits_{j=0}^{n}2^{j}\sum\limits_{i=j}^{n}(-2)^{i-j}\binom{i}{j}x^j \end{aligned} $$ 对 $j=0\sim n$ 求 $\sum\limits_{i=j}^{n}(-2)^{i-j}\binom{i}{j}$ 是容易的，在经典的 P5907 还是讲了在 $a\neq 1$ 的时候 $\sum\limits_{i=n}^{k}\binom{i}{n}a^{i-n}$ 怎么推。 $$ \begin{aligned} T(0)&=\sum\limits_{i=1}^{k}a^i=\frac{a^{k+1}-1}{a-1} \\ T(n)&=\sum\limits_{i=n}^{k}\binom{i}{n}a^{i-n}\\ &=\sum\limits_{i=n}^{k}\left[\binom{i-1}{n}+\binom{i-1}{n-1}\right]a^{i-n}\\ &=a\sum\limits_{i-1=n}^{k-1}\binom{i-1}{n}a^{i-1-n}+\sum\limits_{i-1=n-1}^{k-1} \binom{i-1}{n-1}a^{(i-1)-(n-1)}\\ &=a(T(n)-\binom{k}{n}a^{k-n})+T(n-1)-\binom{k}{n-1}a^{k-n+1}\\ &=aT(n)+T(n-1)-\binom{k+1}{n}a^{k-n+1} \end{aligned} $$ 直接推做就完了，时间复杂度 $O(n)$。 -
P6667 [清华集训2016] 如何优雅地求和
原来的做法是考虑混凝土数学里面讲的下降幂多项式后变成卷积，本题有
x 我们把它换成a 好了。给了点值，相当于给咱们 $b_{X}=\sum\limits_{i=0}^{m} f_{i} [\frac{x^{i}}{i!}](e^{x})^{X}$，求： $$ \sum\limits_{j=0}^mf_{j}[\frac{x^j}{j!}]\sum\limits_{i=0}^{n}\binom{n}{i}a^{i}(1-a)^{n-i}e^{ix} $$ 可以构造出 $F(x)=(ax+(1-a))^n$，终于又遇到需要截断的式子了。 直接上 ODE！还是设 $\mathbb F(x+1)=F(x+1)\bmod x^{m+1} \begin{aligned} anF(x)-(ax-a+1)F'(x)&=0\\ anF(x+1)-(ax+1)F'(x+1)&=0\\ an\mathbb F(x+1)-(ax+1)\mathbb F'(x+1)&=(an-am)x^m[x^m]F(x+1)\\ an\mathbb F(x)-(ax-a+1)\mathbb F'(x)&=(an-am)\binom{n}{m}a^m(x-1)^m\\ (an-ai)f_{i}+(a-1)(i+1)f_{i+1}&=(an-am)\binom{n}{m}\binom{m}{i}a^m(-1)^{m-i} \end{aligned} 然后做完了，时间复杂度
O(m) 。 -
伯努利数
众所周知伯努利数的生成函数是\frac{x}{e^x-1} ，设G(x)=e^x 不难发现F(x)=\frac{\ln x}{x-1} 。咕了