今天好难受啊。
[HEOI2016/TJOI2016]求和
题目描述
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。
现在他想计算这样一个函数的值:
$S(i, j)$表示第二类斯特林数，递推公式为:
$S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1 \le j \le i - 1$。
边界条件为：$S(i, i) = 1(0 \le i), S(i, 0) = 0(1 \le i)$
输出f(n)。由于结果会很大，输出$f(n)$对$998244353(7 × 17 × 223 + 1)$取模的结果即可。
输入输出样例
输入样例#1：
3
输出样例#1：
87
说明
对于50%数据$1 ≤ n ≤5000$
对于100%数据$1 ≤ n ≤ 100000$
题解
等分析报告的时候看的题。。
大致题意： 计算$\sum{i=0}^n\sum{j=0}^iS(i,j)2^j(j!)$，其中$S$为第二类斯特林数。
推式子
首先让我们来推一波式子：
因为当$i < j$时，$S(i,j)=0$，所以，为了方便式子的化简，我们可以先将第二个$\sum$的上限全部改成$n$，即：
这样一来，$\sum_{j=0}^n2^j*(j!)$这个式子就与$i$无关，则我们可以将其提前：
套用第二类斯特林数的通项公式$S(n,m)=\sum_{i=0}^m\frac{(-1)^i*(m-i)^n}{i!(m-i)!}$可以得到：
接下来，我们可以考虑再将所有与$i$无关的项提前，得到下面这个式子：
我们可以枚举$j$，这样前面的$\sum_{j=0}^n2^j*(j!)$一项就可以轻松搞定。
那么接下来的问题就是如何对于给定的$j$，求出下面这个式子的值：
仔细观察，可以发现似乎这个式子前半部分的分母和后半部分都有$(j-k)$这个因式，则容易想到将它们移到一起，即：
这样一移的效果是显著的，因为此时这个式子的前半部分只与$k$有关，后半部分只与$(j-k)$有关。
则可以设$f$和$g$如下：
带入原式就可以得到：
而这个式子实际上就相当于：
至此化简完毕，最终的式子就是：
实现的时候就先$O(n)$预处理出$f$和$g$两个数组，然后$NTT$即可。
我怎么只会抄题解啊qwq
[国家集训队]整数的lqp拆分
题目背景
来源：2011中国国家集训队命题答辩
题目描述
lqp在为出题而烦恼，他完全没有头绪，好烦啊…
他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数N，对于N的一个整数拆分就是满足任意m0，$a1 ,a_2 ,a_3…a_m0$，且$a_1+a_2+a_3+…+a_m=N$的一个有序集合。通过长时间的研究我们发现了计算对于N的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太简单了，如果出这样的题目，大家会对比赛毫无兴趣的。
然后lqp又想到了斐波那契数。定义$F_0=0,F_1=1,F_n=F_n-1+F_n-2 (n1)$，$F_n$就是斐波那契数的第n项。但是求出第n项斐波那契数似乎也不怎么困难…
lqp为了增加选手们比赛的欲望，于是绞尽脑汁，想出了一个有趣的整数拆分，我们暂且叫它：整数的lqp拆分。
和一般的整数拆分一样，整数的lqp拆分是满足任意$m > 0$，$a_1 ,a_2 ,a_3…a_m0$，且$a_1+a_2+a_3+…+a_m=N$的一个有序集合。但是整数的lqp拆分要求的不是拆分总数，相对更加困难一些。
对于每个拆分，lqp定义这个拆分的权值$F{a1}F{a2}…F{am}$，他想知道对于所有的拆分，他们的权值之和是多少？
简单来说，就是求
$\sum\prod{i=1}^m F{a_i}$
$m > 0$
$a_1,a_2…a_m > 0$
$a_1+a_2+…+a_m=N$
由于这个数会十分大，lqp稍稍简化了一下题目，只要输出对于N的整数lqp拆分的权值和$mod (10^9+7)$输出即可。
输入输出格式
输入格式：
输入的第一行包含一个整数N（$N \le 10^6$）。
输出格式：
输出一个整数，为对于N的整数lqp拆分的权值和$mod (10^9+7)$。
输入输出样例
输入样例#1：
3
输出样例#1：
5
说明
$F_0=0,F_1=1,F_2=1,F_3=2$。
对于N=3，有这样几种lqp拆分：
3=1+1+1, 权值是$111=1$。
3=1+2，权值是$12=2$。
3=2+1，权值是$21=2$。
所以答案是$111+12+21=5$。
题解
以前搜索找规律过了这题，今天来认真探讨一下。
首先学过DP的应该能想到一个$O(n^2)$的背包做法。
设$f_i$表示数字$i$的拆分方案乘积和的答案，$F_i$表示Fibonacci number。然后通过枚举$O(n)$个分拆的数乘上原来的子问题答案转移，其实就是加法的分配律。
$fi = \sum\limits{j=1}^{i}f_{i-j}F_j$
要注意考虑到$\{a_i\}$是有序的！
然后我们可以$O(n)$预处理一下斐波那契数列。选择分治NTT$O(nlog^2n)$/多项式求逆$O(nlogn)$来解决这个问题。
但是我们还是有线性做法甚至是一个$O(logn)$的做法。
记号不变。前面说明了：
$fi = \sum\limits{j=1}^{i}f_{i-j}F_j$
我们这里需要定义$f_0 = 0$，这样上面的式子需要改一下，上面是$f_0 = 1$,把$F_i$提出来就行
$F_0 = 0$
$fi = \sum\limits{j=1}^{i-1}f_{i-j}F_j + F_i$
$A(x) = \sum\limits_{i=0}^{\infty}F_ix^i$
$B(x) = \sum\limits_{i=0}^{\infty}f_ix^i$
上面有卷积那我们把这里的形式幂级数$A(x) , B(x) $也卷积一下。
发现$A = A * B + A$
$A(x) = \frac{x}{1-x-x^2}$
解得$B(x) = \frac{x}{1-2x-x^2}$
$x(1-2x-x^2)^{-1}$广义二项式展开后利用特征方程得到$fi = 2f{i-1} + f_{i-2}$
事实上还有更好的做法。
把$B(x)$的封闭表达式化成$\frac{T}{Rx+P} + \frac{H}{Jx+L}$这种形式再广义二项式展开得到的是通项：
$\sqrt{2}$直接求二次剩余即可。时间复杂度$O(logn)$
[TJOI2015]概率论
题目描述
为了提高智商,ZJY开始学习概率论。有一天,她想到了这样一个问题：对于一棵随机生成的n个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢?
判断两棵树是否同构的伪代码如下：
输入输出格式
输入格式：
输入一个正整数n,表示有根树的结点数
输出格式：
输出这棵树期望的叶子节点数,要求误差小于1e-9
输入输出样例
输入样例#1：
1
输出样例#1：
1.000000000
输入样例#2：
3
输出样例#2：
1.200000000
说明
数据范围
对于30%的数据，$1 ≤ n ≤ 10$
对于70%的数据，$1 ≤ n ≤ 100$
对于100%的数据，$1 ≤ n ≤ 10^9$
题解
之所以加粗有根两字是因为我一开始没注意到，结果各种过不了样例。
感觉这题还是很好推的啊qwq？毕竟Catalan数就是个提醒。
至于什么Lagrange反演之类的，我怀疑他肯定是数学竞赛的吧。。。
首先，我们令$f_n$表示$n$个点的二叉树个数；$g_n$表示$n$个点的所有$f_n$棵二叉树的叶节点总数。
找规律第一步当然是打表啦~写个爆搜或者手算都可以。
我们发现一个规律：$gn=nf{n-1}$。
证明这个规律其实超级简单：
对于每棵$n$个点的二叉树，如果里面有$k$个叶节点，那么我们分别把这$k$个叶子删去会得到$k$棵$n-1$个点的二叉树；
而每棵$n-1$个点的二叉树恰好有$n$个位置可以悬挂一个新的叶子，所以每棵$n-1$个点的二叉树被得到了$n$次；
综上，我们即可得出结论：所有$n$个点的二叉树的叶子个数和等于$n-1$个点的二叉树个数$\times n$。
那么我们只需要求出$f$即可。而$f$的递推式可以通过枚举左子树结点个数得到：
边界是$f_1=1$。应该可以一眼看出来这是Catalan数列
于是答案即为
代入卡特兰数的通项公式$f_n=\frac{\binom{2n}{n}}{n+1}$很容易就得到上式等于$\frac{n(n+1)}{2(2n-1)}$。
其实还有一种数学分析来广义二项式展开$\frac{x}{\sqrt{1-4x}}$（形式幂级数卷积后解出来答案的封闭形式）的做法，但是数学太差的我就不班门弄斧了
代码写不写没区别。。。
以上除了第一道需要多项式外，其他都有小学生说是入门题，这不禁让我感觉我对入了OI更加怀疑人生了。