多项式与生成函数

· · 个人记录

多项式与生成函数

普通生成函数

\text{A}

(1,2),(3,8),(4,7),(5,6) f_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)=\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\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}

答案为 \dfrac{(n+2)(n+1)n}{6}

\text{B}

f_i(x)=\sum\limits_{j=0}^{m_i}x^j=\dfrac{1-x^{m_i+1}}{1-x} F(x)=(1-x)^{-n}\prod\limits_{i=1}^n (1-x^{m_i+1})=g(x)h(x) 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\le 10$：求 $h(x)$，时间复杂度 $O(2^n)

次数为 k，设系数为 c_k，对答案贡献为 c_ks_k

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} =\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} 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(2^nn)

\text{C}

求斐波那契数列的生成函数 f(x)

(1-x-x^2)f(x)=a_0x^0+(a_1-a_0)x^1 (1-x-x^2)f(x)=x f(x)=\dfrac{x}{1-x-x^2} g(x)=\sum\limits_{i\ge 0}f(x)^i 令$ $y=f(x)$，$yg(x)=g(x)-1 g(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}

引理：等比数列 {a_n=ck^n} 的生成函数为 \dfrac{c}{1-kx}

证明：f(x)=\sum\limits_{n\ge 0}ck^nx^n

kxf(x)=\sum\limits_{n\ge 1}ck^nx^n (1-kx)f(x)=c f(x)=\dfrac{c}{1-kx}

待定系数：设 h(x)=\dfrac{x}{1-2x-x^2}

h(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=-1 a=\dfrac{\sqrt{2}}{4},b=1+\sqrt{2},c=-\dfrac{\sqrt{2}}{4},d=1-\sqrt{2} h(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)

\sqrt{2}\equiv59713600\pmod{10^9+7}

指数生成函数

\text{F}

t=\dfrac{\sum\limits_d \prod\limits_{i=1}^na_i-\prod\limits_{i=1}^n(a_i-d_i)}{n^k} s=\sum\limits_d \prod\limits_{i=1}^n (a_i-d_i) \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)!} \hat{g}_i(x)=a_ie^x$，$\hat{h}_i(x)=x\sum\limits_{j\ge 0}\dfrac{x^j}{j!}=xe^x \hat{f}_i(x)=(a_i-x)e^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)=\prod\limits_{i=1}^n (a_i-x)=\sum\limits_{i=0}^n c_ix^i

对 e^{nx} 在 x=0 处泰勒展开，得 e^{nx}=\sum\limits_{i\ge 0}\dfrac{n^ix^i}{i!}

\hat{F}(x)=k!(\sum\limits_{i\ge 0}\dfrac{n^ix^i}{i!})(\sum\limits_{i=0}^n c_ix^i) [x^k]\hat{F}(x)=k!\sum\limits_{i=0}^n \dfrac{c_in^{k-i}}{(k-i)!} w=\sum\limits_{i=0}^n \dfrac{c_ik!}{(k-i)!n^i}

答案为 \prod\limits_{i=1}^na_i-w

多项式

\text{K}

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

快速傅里叶变换

f(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)=\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(x^2)+xh(x^2)

引理 1：已知 n 是偶数，\omega_n^i=\cos \dfrac{2\pi i}{n}+\text{i}\sin\dfrac{2\pi i}{n}，则 \omega_n^i=-\omega_n^{i+n/2} 且 \omega_{2n}^{2i}=\omega_n^i

引理 2：已知复数 z_0=z_1z_2，对于 i=\{0,1,2\}，设 r_i=|z_i|,z_i=r_i(\cos\theta_i+\text{i}\theta_i)，则 r_0=r_1r_2，\theta_0=\theta_1+\theta_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)]

引理 3：w_n^n=1

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(\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(\omega_{n/2}^i),h(\omega_{n/2}^i)$，得 $\forall i\in [0,n)\cap \Z,f(i)$，时间复杂度 $O(n\log_2 n)

快速傅里叶逆变换

已知 \forall i\in [0,n)\cap \Z,y_i=f(\omega_n^i)，构造 g(x)=\sum\limits_{i=0}^{n-1}y_ix^i

设 b_i=\omega_n^{-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(\omega_n^x)=\sum\limits_{i=0}^{n-1}\omega_n^{ix}=\sum\limits_{i=0}^{n-1}(\omega_n^x)^i

若 x=0，p(\omega_n^x)=n

若 x\neq 0，p(w)=\dfrac{\omega_n^{nx}-\omega_n^0}{\omega_n^x-1}=0

则 g(b_i)=a_in，即多项式 g 在 b_i 处的点值表示法为 \{(b_i,a_in)|i\in [0,n)\cap \Z\}

位逆序置换

设 x=\sum\limits_{i=0}^k a_i2^i，则 p_x=\sum\limits_{i=0}^ka_{k-i}2^i

p_x=\lfloor\dfrac{p_{\lfloor x/2\rfloor}}{2}\rfloor+(x\mod 2) 2^{k-1}

\text{L}

f(x)=\sum\limits_{i=0}^{n-1}a_ix^i,g(x)=\sum\limits_{i=0}^{n-1}\dfrac{1}{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),p_k=[x^k]F(x)

\text{M}

f(x)=\sum\limits_{i=0}^na_i10^i,g(x)=\sum\limits_{i=0}^mb_i10^i,h(x)=f(x)g(x)

设 q_0=[x^0]h(x),q_i=\lfloor \dfrac{q_{i-1}}{10} \rfloor+[x^i]h(x),p_i=q_i\mod 10

\text{N}

快速数论变换

阶：若 (a,m)=1，则定义满足 a^x\equiv 1\pmod{m} 的正整数 x 的最小值为 \delta_m(a)

原根：若 (a,m)=1,\delta_m(a)=\varphi(m)，则 a 为模 m 的原根

若 n=2^k(k\in \N_+)，p 为质数且 n|(p-1)，g 为 p 的一个原根

设 g_n=g^{\frac{p-1}{n}}，则

引理 1：g_n^n=g^{p-1}\equiv 1\pmod{p}

引理 2：g_n^{n/2}\equiv -1\pmod{p}

证明：g_n^{n/2}=g^{(p-1)/2}

(g^{(p-1)/2})^2\equiv 1\pmod{p} [g^{(p-1)/2}+1][g^{(p-1)/2}-1]\equiv 0\pmod{p}

若 g_n^{n/2}\equiv -1\pmod{p}，则 g^{(p-1)/2}\equiv 1\pmod{p},\delta_p(g)\le \dfrac{p-1}{2}<p-1，不成立

所以 g_n^{n/2}\equiv -1\pmod{p}

引理 3：g_{2n}^{2k}=g^{\frac{2k(p-1)}{2n}}=g^{\frac{k(p-1)}{n}}=g_n^k

\text{O}

已知 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))\equiv 0\pmod{x^{n/2}}，所以 g(x)-h(x)\equiv 0\pmod{x^{n/2}}，设 g(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))x^{n/2}，平方得 g(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\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\equiv 0,g(x)\equiv 2h(x)-f(x)h(x)^2\pmod{x^n}

多项式与生成函数综合

\text{X}

(6,7),(10,4),(3,1),(5,8),(2,9) \forall i\in [1,5]\cap \Z,f_i(x)=\sum\limits_{n\ge 0} x^n f_i(x)=\dfrac{1}{1-x} p=(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

答案为 \dfrac{(n+4)(n+3)(n+2)(n+1)}{24}

\text{Y}

已知 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) 使对于任意的 a，g 为 a 的一阶前缀和的生成函数

令 a_0=0，则 \forall i\in[0,n)\cap \Z,[x^i]g(x)=1，g(x)=\sum\limits_{i\ge 0}x^i=\dfrac{1}{1-x}

则 a 的 k 阶前缀和的生成函数为 f_i(x)=f_0(x)g(x)^k=f_0(x)(1-x)^{-k}

设 h(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