专栏文章

多项式与生成函数

ttrezejs
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mios1fky
此快照首次捕获于
2025/12/03 00:12
3 个月前
此快照最后确认于
2025/12/03 00:12
3 个月前
查看原文

多项式与生成函数

普通生成函数

A\text{A}

(1,2),(3,8),(4,7),(5,6)(1,2),(3,8),(4,7),(5,6)
f1(x)=f2(x)=f4(x)=∑n≥0xn=11−x, f3(x)=∑n≥1xn=x1−xf_1(x)=f_2(x)=f_4(x)=\sum\limits_{n\ge 0} x^n=\dfrac{1}{1-x},\space f_3(x)=\sum\limits_{n\ge 1}x^n=\dfrac{x}{1-x}
f(x)=x(1−x)4=x(1−x)−4=x∑n≥0∏i=0n−1(−4−i)n!(−1)nxnf(x)=\dfrac{x}{(1-x)^4}=x(1-x)^{-4}=x\sum\limits_{n\ge 0} \dfrac{\prod\limits_{i=0}^{n-1}(-4-i)}{n!}(-1)^nx^n
=x∑n≥0(n+3)!3!n!(−1)2nxn=∑n≥1(n+23)xn=x\sum\limits_{n\ge 0}\dfrac{(n+3)!}{3!n!}(-1)^{2n}x^n=\sum\limits_{n\ge 1}\dbinom{n+2}{3} x^{n}
答案为 (n+2)(n+1)n6\dfrac{(n+2)(n+1)n}{6}

B\text{B}

fi(x)=∑j=0mixj=1−xmi+11−xf_i(x)=\sum\limits_{j=0}^{m_i}x^j=\dfrac{1-x^{m_i+1}}{1-x}
F(x)=(1−x)−n∏i=1n(1−xmi+1)=g(x)h(x)F(x)=(1-x)^{-n}\prod\limits_{i=1}^n (1-x^{m_i+1})=g(x)h(x)
g(x)=∑k≥0(−x)k∏i=0k−1(−n−i)k!=∑k≥0xk(n+k−1)!k!(n−1)!=∑k≥0xk(n+k−1k)g(x)=\sum\limits_{k\ge 0} (-x)^k\dfrac{\prod\limits_{i=0}^{k-1}(-n-i)}{k!}=\sum\limits_{k\ge 0} x^k\dfrac{(n+k-1)!}{k!(n-1)!}=\sum\limits_{k\ge 0}x^k\dbinom{n+k-1}{k}
n≤10n\le 10：求 h(x)h(x)，时间复杂度 O(2n)O(2^n)
次数为 kk，设系数为 ckc_k，对答案贡献为 ckskc_ks_k
sk=∑i=a−kb−k(n+i−1i)=(n+a−k−1a−k−1)+(n+a−k−1a−k)+(∑i=a−k+1b−k(n+i−1i))−(n+a−k−1a−k−1)s_k=\sum\limits_{i=a-k}^{b-k}\dbinom{n+i-1}{i}=\dbinom{n+a-k-1}{a-k-1}+\dbinom{n+a-k-1}{a-k}+(\sum\limits_{i=a-k+1}^{b-k}\dbinom{n+i-1}{i})-\dbinom{n+a-k-1}{a-k-1}
=(n+a−ka−k)+(n+a−ka−k+1)+(∑i=a−k+2b−k(n+i−1i))−(n+a−k−1a−k−1)=\dbinom{n+a-k}{a-k}+\dbinom{n+a-k}{a-k+1}+(\sum\limits_{i=a-k+2}^{b-k}\dbinom{n+i-1}{i})-\dbinom{n+a-k-1}{a-k-1}
sk=(n+b−kb−k)−(n+a−k−1a−k−1)=(n+b−kn)−(n+a−k−1n)s_k=\dbinom{n+b-k}{b-k}-\dbinom{n+a-k-1}{a-k-1}=\dbinom{n+b-k}{n}-\dbinom{n+a-k-1}{n}
时间复杂度 O(2nn)O(2^nn)

C\text{C}

求斐波那契数列的生成函数 f(x)f(x)
(1−x−x2)f(x)=a0x0+(a1−a0)x1(1-x-x^2)f(x)=a_0x^0+(a_1-a_0)x^1
(1−x−x2)f(x)=x(1-x-x^2)f(x)=x
f(x)=x1−x−x2f(x)=\dfrac{x}{1-x-x^2}
g(x)=∑i≥0f(x)ig(x)=\sum\limits_{i\ge 0}f(x)^i
令令 y=f(x)y=f(x)，yg(x)=g(x)−1yg(x)=g(x)-1
g(x)=11−f(x)=11−x1−x−x2=1−x−x21−2x−x2=1+x1−2x−x2g(x)=\dfrac{1}{1-f(x)}=\dfrac{1}{1-\dfrac{x}{1-x-x^2}}=\dfrac{1-x-x^2}{1-2x-x^2}=1+\dfrac{x}{1-2x-x^2}
引理：等比数列 an=ckn{a_n=ck^n} 的生成函数为 c1−kx\dfrac{c}{1-kx}
证明：f(x)=∑n≥0cknxnf(x)=\sum\limits_{n\ge 0}ck^nx^n
kxf(x)=∑n≥1cknxnkxf(x)=\sum\limits_{n\ge 1}ck^nx^n
(1−kx)f(x)=c(1-kx)f(x)=c
f(x)=c1−kxf(x)=\dfrac{c}{1-kx}
待定系数：设 h(x)=x1−2x−x2h(x)=\dfrac{x}{1-2x-x^2}
h(x)=a1−bx+c1−dx=(a+c)−(ad+bc)x1−(b+d)x+bdx2h(x)=\dfrac{a}{1-bx}+\dfrac{c}{1-dx}=\dfrac{(a+c)-(ad+bc)x}{1-(b+d)x+bdx^2}
a+c=0,ad+bc=−1,b+d=2,bd=−1a+c=0,ad+bc=-1,b+d=2,bd=-1
a=24,b=1+2,c=−24,d=1−2a=\dfrac{\sqrt{2}}{4},b=1+\sqrt{2},c=-\dfrac{\sqrt{2}}{4},d=1-\sqrt{2}
h(x)=∑n≥024[(1+2)n−(1−2)n]xnh(x)=\sum\limits_{n\ge 0}\dfrac{\sqrt{2}}{4}[(1+\sqrt{2})^n-(1-\sqrt{2})^n]x^n
答案为 g(n)−1=h(n)g(n)-1=h(n)
2≡59713600(mod109+7)\sqrt{2}\equiv59713600\pmod{10^9+7}

指数生成函数

F\text{F}

t=∑d∏i=1nai−∏i=1n(ai−di)nkt=\dfrac{\sum\limits_d \prod\limits_{i=1}^na_i-\prod\limits_{i=1}^n(a_i-d_i)}{n^k}
s=∑d∏i=1n(ai−di)s=\sum\limits_d \prod\limits_{i=1}^n (a_i-d_i)
f^i(x)=∑j≥0(ai−j)xjj!=ai∑j≥0xjj!−∑j≥0jxjj!=ai∑j≥0xjj!−∑j≥1xj(j−1)!\hat{f}_i(x)=\sum\limits_{j\ge 0}\dfrac{(a_i-j)x^j}{j!}=a_i\sum\limits_{j\ge 0}\dfrac{x^j}{j!}-\sum\limits_{j\ge 0}\dfrac{jx^j}{j!}=a_i\sum\limits_{j\ge 0}\dfrac{x^j}{j!}-\sum\limits_{j\ge 1}\dfrac{x^j}{(j-1)!}
g^i(x)=aiex\hat{g}_i(x)=a_ie^x，h^i(x)=x∑j≥0xjj!=xex\hat{h}_i(x)=x\sum\limits_{j\ge 0}\dfrac{x^j}{j!}=xe^x
f^i(x)=(ai−x)ex\hat{f}_i(x)=(a_i-x)e^x
F^(x)=k!∏i=1nf^i(x)=k!enx∏i=1n(ai−x)\hat{F}(x)=k!\prod\limits_{i=1}^n \hat{f}_i(x)=k!e^{nx}\prod\limits_{i=1}^n(a_i-x)
P(x)=∏i=1n(ai−x)=∑i=0ncixiP(x)=\prod\limits_{i=1}^n (a_i-x)=\sum\limits_{i=0}^n c_ix^i
对 enxe^{nx} 在 x=0x=0 处泰勒展开，得 enx=∑i≥0nixii!e^{nx}=\sum\limits_{i\ge 0}\dfrac{n^ix^i}{i!}
F^(x)=k!(∑i≥0nixii!)(∑i=0ncixi)\hat{F}(x)=k!(\sum\limits_{i\ge 0}\dfrac{n^ix^i}{i!})(\sum\limits_{i=0}^n c_ix^i)
[xk]F^(x)=k!∑i=0ncink−i(k−i)![x^k]\hat{F}(x)=k!\sum\limits_{i=0}^n \dfrac{c_in^{k-i}}{(k-i)!}
w=∑i=0ncik!(k−i)!niw=\sum\limits_{i=0}^n \dfrac{c_ik!}{(k-i)!n^i}
答案为 ∏i=1nai−w\prod\limits_{i=1}^na_i-w

多项式

K\text{K}

设 n=2k(k∈N+)n=2^k(k\in \N_+)

快速傅里叶变换

f(x)=∑i=0naixi=∑i=0n2a2ix2i+a2i+1x2i+1f(x)=\sum\limits_{i=0}^n a_ix^i=\sum\limits_{i=0}^{\frac{n}{2}}a_{2i}x^{2i}+a_{2i+1}x^{2i+1}
设 g(x)=∑i=0n2a2ixi,h(x)=∑i=0n2a2i+1xig(x)=\sum\limits_{i=0}^{\frac{n}{2}} a_{2i}x^i,h(x)=\sum\limits_{i=0}^{\frac{n}{2}}a_{2i+1}x^i
f(x)=g(x2)+xh(x2)f(x)=g(x^2)+xh(x^2)
引理 11：已知 nn 是偶数，ωni=cos⁡2πin+isin⁡2πin\omega_n^i=\cos \dfrac{2\pi i}{n}+\text{i}\sin\dfrac{2\pi i}{n}，则 ωni=−ωni+n/2\omega_n^i=-\omega_n^{i+n/2} 且 ω2n2i=ωni\omega_{2n}^{2i}=\omega_n^i
引理 22：已知复数 z0=z1z2z_0=z_1z_2，对于 i={0,1,2}i=\{0,1,2\}，设 ri=∣zi∣,zi=ri(cos⁡θi+iθi)r_i=|z_i|,z_i=r_i(\cos\theta_i+\text{i}\theta_i)，则 r0=r1r2r_0=r_1r_2，θ0=θ1+θ2\theta_0=\theta_1+\theta_2
证明：z0=z1z2=r1r2[cos⁡θ1cos⁡θ2−sin⁡θ1sin⁡θ2+i(cos⁡θ1sin⁡θ2+sin⁡θ1cos⁡θ2)]=r1r2[cos⁡(θ1+θ2)+isin⁡(θ1+θ2)]z_0=z_1z_2=r_1r_2[\cos\theta_1\cos\theta_2-\sin\theta_1\sin\theta_2+\text{i}(\cos\theta_1\sin\theta_2+\sin\theta_1\cos\theta_2)]=r_1r_2[\cos(\theta_1+\theta_2)+\text{i}\sin(\theta_1+\theta_2)]
引理 33：wnn=1w_n^n=1
f(ωni)=g(ωn2i)+ωnih(ωn2i)=g(ωn/2i)+ωnih(ωn/2i)f(\omega_n^i)=g(\omega_n^{2i})+\omega_n^ih(\omega_n^{2i})=g(\omega_{n/2}^i)+\omega_n^ih(\omega_{n/2}^i)
f(ωni+n/2)=g(ωn2i+n)+ωni+n/2h(ωn2i+n)=g(ωn2i)−ωnih(ωn2i)=g(ωn/2i)−ωnih(ωn/2i)f(\omega_n^{i+n/2})=g(\omega_n^{2i+n})+\omega_n^{i+n/2}h(\omega_n^{2i+n})=g(\omega_{n}^{2i})-\omega_n^ih(\omega_{n}^{2i})=g(\omega_{n/2}^i)-\omega_n^ih(\omega_{n/2}^i)
求求 g(ωn/2i),h(ωn/2i)g(\omega_{n/2}^i),h(\omega_{n/2}^i)，得 ∀i∈[0,n)∩Z,f(i)\forall i\in [0,n)\cap \Z,f(i)，时间复杂度 O(nlog⁡2n)O(n\log_2 n)

快速傅里叶逆变换

已知 ∀i∈[0,n)∩Z,yi=f(ωni)\forall i\in [0,n)\cap \Z,y_i=f(\omega_n^i)，构造 g(x)=∑i=0n−1yixig(x)=\sum\limits_{i=0}^{n-1}y_ix^i
设 bi=ωn−ib_i=\omega_n^{-i}，则 g(bi)=∑j=0n−1f(ωnj)ωn−ij=∑j=0n−1ωn−ij∑k=0n−1akωnjk=∑k=0n−1ak∑j=0n−1ωnj(k−i)g(b_i)=\sum\limits_{j=0}^{n-1}f(\omega_n^j)\omega_n^{-ij}=\sum\limits_{j=0}^{n-1}\omega_n^{-ij}\sum\limits_{k=0}^{n-1}a_k\omega_n^{jk}=\sum\limits_{k=0}^{n-1}a_k\sum\limits_{j=0}^{n-1}\omega_n^{j(k-i)}
设 p(ωnx)=∑i=0n−1ωnix=∑i=0n−1(ωnx)ip(\omega_n^x)=\sum\limits_{i=0}^{n-1}\omega_n^{ix}=\sum\limits_{i=0}^{n-1}(\omega_n^x)^i
若 x=0x=0，p(ωnx)=np(\omega_n^x)=n
若 x≠0x\neq 0，p(w)=ωnnx−ωn0ωnx−1=0p(w)=\dfrac{\omega_n^{nx}-\omega_n^0}{\omega_n^x-1}=0
则 g(bi)=aing(b_i)=a_in，即多项式 gg 在 bib_i 处的点值表示法为 {(bi,ain)∣i∈[0,n)∩Z}\{(b_i,a_in)|i\in [0,n)\cap \Z\}

位逆序置换

设 x=∑i=0kai2ix=\sum\limits_{i=0}^k a_i2^i，则 px=∑i=0kak−i2ip_x=\sum\limits_{i=0}^ka_{k-i}2^i
px=⌊p⌊x/2⌋2⌋+(xmod  2)2k−1p_x=\lfloor\dfrac{p_{\lfloor x/2\rfloor}}{2}\rfloor+(x\mod 2) 2^{k-1}

L\text{L}

f(x)=∑i=0n−1aixi,g(x)=∑i=0n−11i2f(x)=\sum\limits_{i=0}^{n-1}a_ix^i,g(x)=\sum\limits_{i=0}^{n-1}\dfrac{1}{i^2}
∀k∈[0,n)∩Z,[xk]f(x)g(x)=∑i=0n−1ai×1(k−i)2\forall k\in [0,n)\cap \Z,[x^k]f(x)g(x)=\sum\limits_{i=0}^{n-1}a_i\times \dfrac{1}{(k-i)^2}
F(x)=f(x)g(x),pk=[xk]F(x)F(x)=f(x)g(x),p_k=[x^k]F(x)

M\text{M}

f(x)=∑i=0nai10i,g(x)=∑i=0mbi10i,h(x)=f(x)g(x)f(x)=\sum\limits_{i=0}^na_i10^i,g(x)=\sum\limits_{i=0}^mb_i10^i,h(x)=f(x)g(x)
设 q0=[x0]h(x),qi=⌊qi−110⌋+[xi]h(x),pi=qimod  10q_0=[x^0]h(x),q_i=\lfloor \dfrac{q_{i-1}}{10} \rfloor+[x^i]h(x),p_i=q_i\mod 10

N\text{N}

快速数论变换

阶：若 (a,m)=1(a,m)=1，则定义满足 ax≡1(modm)a^x\equiv 1\pmod{m} 的正整数 xx 的最小值为 δm(a)\delta_m(a)
原根：若 (a,m)=1,δm(a)=φ(m)(a,m)=1,\delta_m(a)=\varphi(m)，则 aa 为模 mm 的原根
若 n=2k(k∈N+)n=2^k(k\in \N_+)，pp 为质数且 n∣(p−1)n|(p-1)，gg 为 pp 的一个原根
设 gn=gp−1ng_n=g^{\frac{p-1}{n}}，则
引理 11：gnn=gp−1≡1(modp)g_n^n=g^{p-1}\equiv 1\pmod{p}
引理 22：gnn/2≡−1(modp)g_n^{n/2}\equiv -1\pmod{p}
证明：gnn/2=g(p−1)/2g_n^{n/2}=g^{(p-1)/2}
(g(p−1)/2)2≡1(modp)(g^{(p-1)/2})^2\equiv 1\pmod{p}
[g(p−1)/2+1][g(p−1)/2−1]≡0(modp)[g^{(p-1)/2}+1][g^{(p-1)/2}-1]\equiv 0\pmod{p}
若 gnn/2≡−1(modp)g_n^{n/2}\equiv -1\pmod{p}，则 g(p−1)/2≡1(modp),δp(g)≤p−12<p−1g^{(p-1)/2}\equiv 1\pmod{p},\delta_p(g)\le \dfrac{p-1}{2}<p-1，不成立
所以 gnn/2≡−1(modp)g_n^{n/2}\equiv -1\pmod{p}
引理 33：g2n2k=g2k(p−1)2n=gk(p−1)n=gnkg_{2n}^{2k}=g^{\frac{2k(p-1)}{2n}}=g^{\frac{k(p-1)}{n}}=g_n^k

O\text{O}

已知 f(x)g(x)≡1(modxn),f(x)h(x)≡1(modxn/2)f(x)g(x)\equiv 1\pmod{x^n},f(x)h(x)\equiv 1\pmod{x^{n/2}}，则 f(x)(g(x)−h(x))≡0(modxn/2)f(x)(g(x)-h(x))\equiv 0\pmod{x^{n/2}}，所以 g(x)−h(x)≡0(modxn/2)g(x)-h(x)\equiv 0\pmod{x^{n/2}}，设 g(x)=a(x)+b(x)xn/2,h(x)=a(x)+c(x)xn/2g(x)=a(x)+b(x)x^{n/2},h(x)=a(x)+c(x)x^{n/2}，则 g(x)−h(x)=(b(x)−c(x))xn/2g(x)-h(x)=(b(x)-c(x))x^{n/2}，平方得 g(x)2−2g(x)h(x)+h(x)2=(b(x)−c(x))2xng(x)^2-2g(x)h(x)+h(x)^2=(b(x)-c(x))^2x^n，所以
g(x)2−2g(x)h(x)+h(x)2≡0(modxn),f(x)g(x)2−2f(x)g(x)h(x)+f(x)h(x)2≡0(modxn)g(x)^2-2g(x)h(x)+h(x)^2\equiv 0\pmod{x^n},f(x)g(x)^2-2f(x)g(x)h(x)+f(x)h(x)^2\equiv 0\pmod{x^n}
g(x)−2h(x)+f(x)h(x)2≡0,g(x)≡2h(x)−f(x)h(x)2(modxn)g(x)-2h(x)+f(x)h(x)^2\equiv 0,g(x)\equiv 2h(x)-f(x)h(x)^2\pmod{x^n}

多项式与生成函数综合

X\text{X}

(6,7),(10,4),(3,1),(5,8),(2,9)(6,7),(10,4),(3,1),(5,8),(2,9)
∀i∈[1,5]∩Z,fi(x)=∑n≥0xn\forall i\in [1,5]\cap \Z,f_i(x)=\sum\limits_{n\ge 0} x^n
fi(x)=11−xf_i(x)=\dfrac{1}{1-x}
p=(1−x)−5=∑n≥0∏i=0n−1(−5−i)n!(−1)nxn=∑n≥0(−1)n(n+4)!4!n!(−1)nxn=∑n≥0(n+44)xnp=(1-x)^{-5}=\sum\limits_{n\ge 0}\dfrac{\prod\limits_{i=0}^{n-1}(-5-i)}{n!}(-1)^nx^n=\sum\limits_{n\ge 0}\dfrac{(-1)^n(n+4)!}{4!n!}(-1)^nx^n=\sum\limits_{n\ge 0}\dbinom{n+4}{4}x^n
答案为 (n+4)(n+3)(n+2)(n+1)24\dfrac{(n+4)(n+3)(n+2)(n+1)}{24}

Y\text{Y}

已知 f0(x)=∑i=1naixi,f1(x)=f0(x)g(x),si=[xi]f1(x)f_0(x)=\sum\limits_{i=1}^na_ix^i,f_1(x)=f_0(x)g(x),s_i=[x^i]f_1(x)，求 g(x)g(x) 使对于任意的 aa，gg 为 aa 的一阶前缀和的生成函数
令 a0=0a_0=0，则 ∀i∈[0,n)∩Z,[xi]g(x)=1\forall i\in[0,n)\cap \Z,[x^i]g(x)=1，g(x)=∑i≥0xi=11−xg(x)=\sum\limits_{i\ge 0}x^i=\dfrac{1}{1-x}
则 aa 的 kk 阶前缀和的生成函数为 fi(x)=f0(x)g(x)k=f0(x)(1−x)−kf_i(x)=f_0(x)g(x)^k=f_0(x)(1-x)^{-k}
设 h(x)=(1−x)−k=∑i≥0∏j=0i−1(−k−j)i!(−1)ixi=∑i≥0(k+i−1)!i!(k−1)!xi=∑i≥0(k+i−1i)xih(x)=(1-x)^{-k}=\sum\limits_{i\ge 0}\dfrac{\prod\limits_{j=0}^{i-1}(-k-j)}{i!}(-1)^ix^i=\sum\limits_{i\ge 0}\dfrac{(k+i-1)!}{i!(k-1)!}x^i=\sum\limits_{i\ge 0}\dbinom{k+i-1}{i}x^i

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...