Post 92

今天好难受啊。

[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,$a_1 ,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,权值是$2
1=2$。
所以答案是$111+12+21=5$。

题解

以前搜索找规律过了这题,今天来认真探讨一下。

首先学过DP的应该能想到一个$O(n^2)$的背包做法。

设$f_i$表示数字$i$的拆分方案乘积和的答案,$F_i$表示Fibonacci number。然后通过枚举$O(n)$个分拆的数乘上原来的子问题答案转移,其实就是加法的分配律。

$f_i = \sum\limits_{j=1}^{i}f_{i-j}F_j$

要注意考虑到$\{a_i\}$是有序的!

然后我们可以$O(n)$预处理一下斐波那契数列。选择分治NTT$O(nlog^2n)$/多项式求逆$O(nlogn)$来解决这个问题。

但是我们还是有线性做法甚至是一个$O(logn)$的做法。

记号不变。前面说明了:

$f_i = \sum\limits_{j=1}^{i}f_{i-j}F_j$

我们这里需要定义$f_0 = 0$,这样上面的式子需要改一下,上面是$f_0 = 1$,把$F_i$提出来就行

$F_0 = 0$

$f_i = \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}$广义二项式展开后利用特征方程得到$f_i = 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$棵二叉树的叶节点总数。
找规律第一步当然是打表啦~写个爆搜或者手算都可以。

我们发现一个规律:$g_n=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更加怀疑人生了。