P4451 [国家集训队]整数的lqp拆分
求
\[\sum_{\sum_{i=1}^{m}a_i=n,a_i>0}\prod_{i=1}^{m}f_{a_i}
\]
\(f\) 是斐波那契数列，\(f_0=0\)，\(f_1=1\).
答案对 \(1e9+7\) 取模。\(n\le 10^{10^4}\).
纯数学题。
记斐波那契数列的生成函数，即
\[F(x)=\sum_{i=0}^{+\infty}f_ix^i
\]
那么
\[F(x)=f_0+f_1x+f_2x^2+f_3x^3+f_4x^4+\dots
\]
\[xF(x)=f_0x+f_1x^2+f_2x^3+f_3x^4+\dots
\]
\[x^2F(x)=f_0x^2+f_1x^3+f_2x^4+\dots
\]
分别记为 \((1),(2),(3)\).
\((2)+(3)\)，由 \(f_i=f_{i-1}+f_{i-2}\) 得
\[(x+x^2)F(x)=f_2x^2+f_3x^3+f_4x^4+\dots
\]
那么
\[F(x)=(x+x^2)F(x)+x
\]
\[F(x)=\frac{x}{1-x-x^2}
\]
其实分母长得有点像 \(f\) 的特征多项式。
设 \(g_n\) 为 \(n\) 处的答案。
\[g_n=\sum_{i=0}^{n}g_if_{n-i}
\]
边界 \(g_0=1\).
\[g_n=\lbrack n=0\rbrack+\sum_{i=0}^{n}g_if_{n-i}
\]
设 \(g\) 的生成函数 \(G(x)=\sum_{i=0}^{+\infty}g_ix^i\)，展开得
\[G(x)=\sum_{n=0}^{+\infty}(\lbrack n=0\rbrack+\sum_{i=0}^{n}g_if_{n-i})x^n
\]
\[G(x)=1+\sum_{n=1}^{+\infty}(\sum_{i=0}^{n}g_if_{n-i})x^n
\]
显然右式 \(=F(x)\times G(x)\).
因此
\[G(x)=1+F(x)\times G(x)
\]
\[G(x)=\frac{1}{1-F(x)}=\frac{1}{1-\frac{x}{1-x-x^2}}
\]
\[=\frac{1-x-x^2}{1-2x-x^2}=1-\frac{x}{x^2+2x-1}
\]
考虑展开 \(-\frac{x}{x^2+2x-1}\)：
\(x^2+2x-1=0\) 的两根为 \(x_{1,2}=-1\pm\sqrt{2}\).
\[-\frac{x}{x^2+2x-1}=-\frac{x}{(x-x_1)(x-x_2)}
\]
\[=\frac{x}{x_2-x_1}(\frac{1}{x-x_1}-\frac{1}{x-x_2})
\]
括号里其实是 \(\frac{x_2-x_1}{(x-x_1)(x-x_2)}\).
往 \(\frac{1}{1-x}=\sum_{i=0}^{+\infty}x^i\) 去靠，将常数项化为 \(1\)：
\[=\frac{x}{x_2-x_1}(\frac{1}{x_2}\times\frac{1}{1-\frac{x}{x_2}}-\frac{1}{x_1}\times\frac{1}{1-\frac{x}{x_1}})
\]
\[=\frac{x}{x_2-x_1}(\frac{1}{x_2}\times\sum_{i=0}^{+\infty}\frac{x^i}{x_2^i}-\frac{1}{x_1}\sum_{i=0}^{+\infty}\frac{x^i}{x_1^i})
\]
\[=\frac{1}{x_2-x_1}(\sum_{i=0}^{+\infty}\frac{x^{i+1}}{x_2^{i+1}}-\frac{x^{i+1}}{x_1^{i+1}})
\]
第 \(n\) 项的系数为
\[g(n)=\frac{1}{x_2-x_1}\times(\frac{1}{x_2^n}-\frac{1}{x_1^n})
\]
代入得
\[g(n)=\frac{\sqrt{2}}{4}\lbrack(1+\sqrt{2})^n-(1-\sqrt{2})^n\rbrack
\]
同余方程
\[x\equiv\sqrt{2}\mod 1e9+7
\]
的解为 \(x_1=59713600\)，\(x_2=940286407\).
困难。
P4389 付公主的背包
\(n\) 个物品，每个体积 \(v_i\)，对于 \(s\in\lbrack 1,m\rbrack\) 问刚好装 \(s\) 体积的方案数。答案对 \(998244353\) 取模。
\(1\le n,m\le 10^5\).
对于单个 \(V\) 的生成函数是
\[A(x)=\sum_{i=0}^{+\infty}\lbrack V|i\rbrack x^i=\frac{1}{1-x^V}
\]
答案的生成函数 \(F\) 是所有生成函数的卷积。
两边取对数：
\[\ln F=\sum_{i=1}^{n}\ln \frac{1}{1-x^{v_i}}
\]
- \(\displaystyle \ln (1-x^V)=-\sum_{i=1}^{+\infty}\frac{x^{iV}}{i}\).
\[\ln F(x)=G(x)
\]
\[\frac{F'(x)}{F(x)}=G'(x)
\]
\[\frac{-Vx^{V-1}}{1-x^V}=G'(x)
\]
因为 \(\displaystyle\frac{1}{1-x^V}=\sum_{i\ge0}x^{iV}\)：
\[-\sum_{i\ge0}Vx^{V-1+iV}=G'(x)
\]
\[-\sum_{i\ge0}\frac{Vx^{V+iV}}{V+iV}=G(x)
\]
\[-\sum_{i\ge1}\frac{x^{iV}}{i}=G(x)
\]
相当于 \(O(m \log m)\) 求了 \(\ln\) 又求了和。
\(\exp\) 然后求逆即可。
record
The Child and Binary Tree
我测 *3100.
对于 \(s\in\lbrack1,m\rbrack\)，求各点权都在集合 \(\{c\}\) 内的，点权和为 \(s\) 的有根二叉树总数。答案对 \(998244353\) 取模。
值域 \(10^5\).
记 \(f_i\) 为符合题意且点权和为 \(i\) 的二叉树个数，\(g_i=\lbrack i\in\{c\}\rbrack\).
\[f_n=\sum_{i=1}^{n}g_i\sum_{i=1}^{n-i}f_jf_{n-i-j}
\]
边界值 \(f_0=1\).
令 \(F,G\) 分别为 \(f,g\) 的生成函数，则
\[F=G\cdot F^2+1
\]
由求根公式得
\[F=\frac{1\pm\sqrt{1-4G}}{2G}
\]
然后一个奇怪理论：
若为 \(+\) 号，\(\displaystyle\lim_{x\rightarrow0}F(x)=+\infty\)，舍去。
若为 \(-\) 号，\(\displaystyle\lim_{x\rightarrow0}F(x)=1\)，符合。
\[F=\frac{1-\sqrt{1-4G}}{2G}
\]
\[F=\frac{2}{1+\sqrt{1-4G}}
\]
开根+求逆。
record
P4841 [集训队作业2013] 城市规划
求出 \(
n\) 个点的简单有标号无向连通图数目。答案对 \(1004535809=479\times 2^{21}+1\) 取模。
\(n\le 130000\).
记 \(g_n\) 为 \(n\) 个节点的有标号无向图个数，即 \(g_n=2^{\frac{n(n-1)}{2}}\).
记 \(f_n\) 为 \(n\) 个节点的有标号无向连通图个数，考虑 \(1\) 所在连通块的节点数 \(k\)，有
\[g_n=\sum_{k=1}^{n}\binom{n-1}{k-1}f_kg_{n-k}
\]
把组合数拆开：
\[\frac{g_n}{(n-1)!}=\sum_{k=1}^{n}\frac{f_k}{(k-1)!}\cdot\frac{g_{n-k}}{(n-k)!}
\]
变成了卷积的形式。
记
\[F(x)=\sum_{n=1}^{+\infty}\frac{f_n}{(n-1)!}x^n
\]
\[G(x)=\sum_{n=0}^{+\infty}\frac{g_n}{n!}x^n
\]
\[H(x)=\sum_{n=1}^{+\infty}\frac{g_n}{(n-1)!}x^n
\]
那么有 \(H=F\times G\)，故 \(F= H\times G^{-1}\)，答案为 \(F_n\cdot (n-1)!\).
多项式求逆+乘法即可。
record（为什么跑不过大样例也AC了）
P4491 [HAOI2018] 染色
\(n\) 个格子可以染 \(m\) 种颜色，若有 \(k\) 种出现次数恰好为 \(S\) 的颜色，贡献为 \(W_k\).
求所有染色方案的总贡献对 \(1004535809
\) 取模的结果。
\(n\le 10^7\)，\(m\le 10^5\)，\(S\le 150\).
这个模数一眼多项式。
记 \(k\) 的上界 \(lim=\min(m,\lfloor\frac{n}{S}\rfloor)\).
容斥，计算出现 \(S\) 次的有至少 \(i\) 种的方案数 \(g_i\).
钦定 \(i\) 种颜色各 \(S\) 个，其余 \(m-i\) 种颜色共 \(n-iS\) 个，加上可重全排列即
\[g_i=\binom{m}{i}\cdot\frac{n!}{(S!)^i(n-iS)!}\cdot(m-i)^{n-iS}
\]
记正好 \(i\) 种的为 \(f_i\)，二项式反演
\[f_i=\sum_{j=1}^{lim}(-1)^{j-i}\cdot\binom{j}{i}\cdot g_j
\]
\[=\sum_{j=i}^{lim}(-1)^{j-i}\cdot\frac{j!}{i!(j-i)!}\cdot g_j
\]
那么
\[f_i\cdot i!=\sum_{j=i}^{lim}\frac{(-1)^{j-i}}{(j-i)!}\cdot g_j\cdot j!
\]
令
\[F(x)=\frac{(-1)^x}{x!}
\]
\[G(x)=g_x\cdot x!
\]
有
\[f_k=\frac{1}{k!}\sum_{i=k}^{lim}F(i-k)G(i)
\]
\[f_k=\frac{1}{k!}\sum_{i=0}^{lim-k}F(i)G(i+k)
\]
这里的卷积可以用 [ZJOI2014]力 的套路，记 \(G\) 反转后的函数 \(G'\) 满足 \(G'(x)=G(lim-x)\)，即
\[f_k=\frac{1}{k!}\sum_{i=0}^{lim-k}F(i)G'(lim-k-i)
\]
把 \(F\) 和 \(G'\) 卷起来，记为 \(H\)，那么 \(f_k\) 对应的就是 \(H(lim-k)\).
答案为
\[\sum_{i=0}^{lim}W_i\cdot\frac{1}{i!}\cdot H(lim-i)
\]
时间复杂度 \(O(m\log m)\).
2023.7.9 23:44 水杯哥的热点就是好用
P5488 差分与前缀和
求长为 \(n\) 的序列 \(a\) 的 \(k\) 阶差分或前缀和。
答案对 \(1004535809\) 取模。
把 \(a\) 看成一个 OGF
\[F(x)=\sum_{i=0}^{\infty}a_ix^i
\]
计算前缀和只需让 \(F\) 卷上 \(\displaystyle G(x)=\sum_{i=0}^{\infty}x^i=\frac{1}{1-x}\).
同理计算差分让 \(F\) 卷上 \(G(x)=1-x\) 即可。
\(k\) 阶前缀和即 \(\displaystyle F\times(\frac{1}{1-x})^k\).
\(k\) 阶差分即 \(F\times (1-x)^k\).
record
P5748 集合划分计数
贝尔数 \(B_n\) 表示将 \(n\) 个元素划分若干非空子集的方案数。
\(1000\) 组数据求 \(B_n(n\le 10^5)\)，答案对 \(998244353\) 取模。
考虑递推：
\[B_n=\sum_{k=0}^{n-1}\binom{n-1}{k}B_{n-k-1}
\]
\[B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_{n-k}
\]
设 \(B_n\) 的 EGF 为 \(B(x)\)，即 \(\displaystyle\sum_{i=0}^{\infty}B_i\cdot \frac{x^i}{i!}\).
那么
\[\frac{B_{n+1}}{(n+1)!}=\sum_{i=0}^{n}\frac{B_{n-i}}{(n-i)!}\cdot\frac{1}{(n+1)i!}
\]
\[(n+1)\cdot\frac{B_{n+1}}{(n+1)!}=\sum_{i=0}^{n}\frac{B_{n-i}}{(n-i)!}\cdot\frac{1}{i!}
\]
数列 \(a_i=1\) 的 EGF 为 \(F(x)=e^x\)，证明需要用到泰勒展开。
\[[x^n]B'(x)=\sum_{i=0}^{n}[x^{n-i}]B(x)\cdot[x^i]e^x
\]
\[B'(x)=B(x)e^x
\]
\[\frac{dB(x)}{dx}=B(x)e^x
\]
\[\frac{dy}{dx}=e^x y
\]
\[\int\frac{dy}{y}=\int e^x dx
\]
\[\ln y=e^x+C
\]
\[y=e^{e^x+C}
\]
由 \(B_0=1\) 可得 \(C=-1\).
故有 \(B(x)=e^{e^x-1}\)，那么 \(B_x=B(x)\cdot x!\).
对 \(\displaystyle F(x)=-1+\sum_{i=0}^{\infty}\frac{1}{i!}x^i=\sum_{i=1}^{\infty}\frac{1}{i!}x^i\) 做一遍 exp 即可。
record
P5824 十二重计数法
求将 \(n\) 个球放进 \(m\) 个盒子里的方案数。
答案对 \(998244353\) 取模。值域 \(\rm2e5\).
假设 \(n,m\) 同阶。
\(1.\) 球有标号，盒子有标号
答案为 \(m^n\).
\(2.\) 球有标号，盒子有标号，盒子至多放一个
每次挑一个未选的，答案为 \(m^{\underline n}\).
\(3.\) 球有标号，盒子有标号，盒子至少装一个
容斥，枚举空盒数，答案为
\[\sum_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n
\]
\(4.\) 球有标号，盒子无标号
考虑第二类斯特林数，答案为 \(\displaystyle\sum_{i=1}^{m}\begin{Bmatrix}n\\i\end{Bmatrix}\).
把模板搬上来，时间复杂度 \(O(n\log n)\).
\(5.\) 球有标号，盒子无标号，盒子至多装一个
思考一下就是无论怎么放都是一样的，答案为 \([n\le m]\).
\(6.\) 球有标号，盒子无标号，盒子至少装一个
答案即 \(\displaystyle\begin{Bmatrix}n\\m\end{Bmatrix}\).
\(7.\) 球无标号，盒子有标号
利用插板法得答案为 \(\displaystyle\binom{n+m-1}{m-1}\).
\(8.\) 球无标号，盒子有标号，盒子至多装一个
即选出 \(n\) 个盒子装球，答案为 \(\displaystyle\binom{m}{n}\).
\(9.\) 球无标号，盒子有标号，盒子至多装一个
先钦定每个盒子都放了一个再插板，答案为 \(\displaystyle\binom{n-1}{m-1}\).
\(10.\) 球无标号，盒子无标号
记划分数 \(p_{n,m}\) 为将 \(n\) 划分为 \(m\) 个自然数的可重集的拆分数，有
\[p_{i,j}=p_{i-j,j}+p_{i,j-1}
\]
意思就是将 \(j\) 个自然数同时 \(+1\) 或将一个 \(0\) 加入可重集中，计数是不重不漏的。
构造多项式
\[F_i(x)=\sum_{j=0}^{i}p_{j,i}x^j
\]
那么
\[F_i(x)=F_{i-1}(x)\times(1+x^i+x^{2i}+\dots)
\]
\[F_i(x)=\frac{F_{i-1}(x)}{1-x^i}
\]
\[F_i(x)=\prod_{j=1}^{i}\frac{1}{1-x^j}
\]
这里就和付公主的背包一样了，一并复制过来。时间复杂度 \(O(n\log n)\).
\(11.\) 球无标号，盒子无标号，盒子至多装一个
和 \(5.\) 一样，答案为 \([n\le m]\).
\(12.\) 球无标号，盒子无标号，盒子至少装一个
与 \(7.\rightarrow9.\) 一样，答案为 \(p_{n-m,m}\).
总时间复杂度 \(O(n\log n)\).
record
P2000 拯救世界
根据题意，把下面十个生成函数乘起来：
\[1+x^6+x^{12}+\dots=\frac{1}{1-x^6}
\]
\[1+x+\dots+x^9=\frac{1-x^{10}}{1-x}
\]
\[1+x+\dots+x^5=\frac{1-x^6}{1-x}
\]
\[1+x^4+x^8+\dots=\frac{1}{1-x^4}
\]
\[1+x+\dots+x^7=\frac{1-x^8}{1-x}
\]
\[1+x^2+x^4+\dots=\frac{1}{1-x^2}
\]
\[1+x=\frac{1-x^2}{1-x}
\]
\[1+x^8+x^{16}+\dots=\frac{1}{1-x^8}
\]
\[1+x^{10}+x^{20}+\dots=\frac{1}{1-x^{10}}
\]
\[1+x+\dots+x^3=\frac{1-x^4}{1-x}
\]
即 \(\displaystyle\frac{1}{(1-x)^5}\).
思考怎么求这个东西的 \(n\) 次项。
假设组合数推广到负数，且对于整数 \(n<0\)，\(m\ge0\)：
\[\binom{n}{m}=\frac{n(n-1)(n-2)\dots(n-m+1)}{m!}
\]
首先有
\[(x+1)^n=\sum_{i=0}^{\infty}\binom{n}{i}x^i
\]
将指数推广至负数,此时的组合数即：
\[\binom{-n}{m}=\frac{(-n)(-n-1)\dots(-n-m+1)}{m!}
\]
把分子的所有项取反：
\[\binom{-n}{m}=(-1)^{(-n)-(-n-m+1)+1}\cdot\frac{n(n+1)\dots(n+m-1)}{m!}
\]
\[=(-1)^m\cdot\binom{n+m-1}{m}
\]
那么
\[(x+1)^{-n}=\sum_{i=0}^{\infty}\binom{-n}{i}x^i=\sum_{i=0}^{\infty}(-1)^i\binom{n+i-1}{i}x^i
\]
从最初的开始，考虑将 \(x\) 取负：
\[(1-x)^n=\sum_{i=0}^{\infty}(-1)^i\binom{n}{i}x^i
\]
把这里的 \(n\) 也取负：
\[(1-x)^{-n}=\sum_{i=0}^{\infty}\binom{n+i-1}{i}x^i
\]
把 \(n'=5\) 代入：
\[[x^n]\frac{1}{(1-x)^5}=\binom{n+5-1}{n}
\]
\[=\binom{n+4}{n}=\binom{n+4}{4}
\]
答案就是 \(\displaystyle\frac{(n+1)(n+2)(n+3)(n+4)}{24}\).
本题大数相乘还要至少弄两遍 \(\rm poly\)。最后暴力除以 \(24\).
record
P3784 [SDOI2017] 遗忘的集合
付公主的背包逆向版。给出方案总数 \(f\)，还原集合 \(S\).
也就是有
\[F_i(x)=\Big(\sum_{n\ge0}x^{ni}\Big)^{a_i}=\Big(\ \frac{1}{1-x^i}\Big)^{a_i}
\]
已知
\[F(x)=\prod_{i=1}^{n} F_i(x)
\]
试还原 \(\{a_i\}\).
\(1\le n<2^{18}\)，\(10^6\le p<2^{30}\)，\(0\le f(i)<p\).
本题需要使用 \(\rm MTT\).
不难想到两边取 \(\ln\)：
\[\ln F(x)=-\sum_{i\ge1}a_i\ln(1-x^i)
\]
\[=\sum_{i\ge1}a_i\sum_{n\ge1}\frac{x^{ni}}{n}
\]
考虑枚举 \(t=ni\)：
\[\sum_{t\ge1}\sum_{i|t}a_i\cdot\frac{x^t}{t/i}=\sum_{t\ge1}\Bigg(\sum_{i|t}a_i\frac{i}{t}\Bigg)\cdot x^t
\]
那么
\[[x^t]\ln F(x)=\sum_{i|t}a_i\frac{i}{t}
\]
\[t[x^t]\ln F(x)=\sum_{i|t}a_ii
\]
考虑数论函数
\[f(n)=n[x^n]\ln F(x)
\]
\[g(n)=a_nn
\]
那么
\[f=g * I
\]
\[f * \mu=g
\]
容易发现答案是唯一的。
学习一下 zhiyangfan 的 MTT \(\ln\) 板子。
record