『湖南省队集训』lcm

题目

题目描述

给出$A,B$,考虑所有满足$1\le a\le A$,$1\le b\le B$,且不存在$n>1$使得$n^2$同时整除$a$和$b$的有序数对$(a,b)$,求其${\mathrm{lcm}}(a,b)$之和。答案模$2^{30}$。

输入格式

第一行一个整数$T$表示数据组数。接下来$T$行每行两个整数$A,B$表示一组数据。

输出格式

对每组数据输出一行一个整数表示答案模$2^{30}$的值。

样例输入

5
2 2
4 6
3 4
5 1
23333 33333

样例输出

7
148
48
15
451085813

数据范围

对于$20\%$数据,$T\le 10$,$A,B\le 500$。

对于$30\%$数据,$T\le 10$,$A,B\le 2000$。

对于$40\%$数据,$T\le 10$,$A,B\le 2\times 10^5$。

对于$60\%$数据,$T\le 10$,$A,B\le 4\times 10^6$。

对于所有数据,$T\le 2000$,$A,B\le 4\times 10^6$。

『湖南省队集训』rescue

题目

题目描述

wyh8000很喜欢看书, 特别是那种很容易死脑细胞的书。

wyh8000看书喜欢从第$K$页开始看起,然后看到第$M$页,但是wyh8000并不是有耐心的小盆友,他只想快点完成看书任务,然后就可以去愉快的农别人了,于是他经常跳着看,但是他一次最多跳$D$页,然后阅读那一页的内容,然后死掉$A$的脑细胞。当然如果那一页的内容他比较感兴趣,又会回复一定的脑细胞。

好心的学长不希望看到wyh8000的脑细胞死光,你能帮助wyh8000死掉尽可能少的脑细胞吗?

输入格式

第一行五个非负整数$K,M,D,A,N$。

$K,M,D,A$如题目描述。$N$表示有$N$页wyh8000比较感兴趣。

接下来$N$行,每一行两个正整数,$T_i,B_i$,表示当wyh8000阅读第$T_i$页时,能回复$B_i$的脑细胞。

输出格式

一个整数$ans$。表示能拯救的最多的脑细胞数,若最后还是损失则为负数。

样例输入

0 10 4 10 2
3 10
8 5

样例输出

-20

样例解释

wyh8000从第$0$页开始看。

wyh8000跳到第$3$页,损失$10$脑细胞。

wyh8000阅读第$3$页,拯救$10$脑细胞。

wyh8000跳到第$7$页并阅读,损失$10$脑细胞。

wyh8000跳到第$10$页并阅读,损失$10$脑细胞。

学长最后无能为力,但是损失$20$是最优的策略,所以输出为$-20$。

数据范围

对于全部数据,$1\le B_i,A,D\le 10^9$,$1\le N\le 10^5$。$0\le K<T_1<T_2<\dots<T_N<M\le 10^9$。

对于$20\%$数据,$N\le 1000$;

对于另$30\%$数据,$D\le 100$。

『湖南省队集训』tower

题目

题目描述

Nick最近在玩一款很好玩的游戏,游戏规则是这样的:

有一个$n\times m$的地图,地图上的每一个位置要么是空地,要么是炮塔,要么是一些BETA狗,Nick需要操纵炮塔攻击BETA狗们。

攻击方法是:对于每个炮塔,游戏系统已经给出它可以瞄准的方向(上下左右其中一个),Nick需要选择它的攻击位置,每一个炮塔只能够攻击一个位置,炮塔只能够向着它的瞄准方向上的某个位置发动攻击,当然炮塔也可以不进行攻击。炮塔威力强大,它可以且仅可以消灭目标位置上所有的BETA狗。

出于安全考虑,游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔,即对于任意一个炮塔,它所有可能的攻击位置上不存在另外一个炮塔。而且,如果把炮塔的起点和终点称为炮弹的运行轨迹,那么系统不允许两条轨迹相交(包括起点和终点)。

现在,选定目标位置以后,每一个炮塔同时开炮,你要告诉Nick,他最多可以干掉多少BETA狗。

输入格式

第一行两个正整数$n,m$,表示地图的规模。

接下来$n$行,每行$m$个整数,$0$表示空地,$-1$,$-2$,$-3$,$-4$分别表示瞄准上下左右的炮塔,若为正整数$p$,则表示该位置有$p$个BETA狗。

输出格式

一行一个正整数,表示Nick最多可以干掉几个BETA狗。

样例输入 1

3 2
0 9
-4 3
0 -1

样例输出 1

9

样例输入 2

4 5
0 0 -2 0 0
-4 0 5 4 0
0 -4 3 0 6
9 0 0 -1 0

样例输出 2

12

样例解释

对于样例$1$,由于轨迹不能相交,那么只能由最下面的炮塔攻击位置$(1,2)$。

对于样例$2$,可以由$(2,1),(3,2),(4,4)$三个炮塔解决$5+3+4=12$个BETA狗。

数据范围

对于$20\%$的数据,$n, m\le 5$。

对于另外$20\%$的数据,最多有$2$个朝向上下的炮塔。

对于另外$20\%$的数据,最多有$6$个炮塔。

对于$100\%$的数据,$n, m\le 50$,每个位置的BETA狗数量不超过$999$个,保证不存在任意一个炮塔能够瞄准另外一个炮塔。

『湖南省队集训』simplest

题目

永远不要被题目名所蒙骗。

题目描述

有一个$n$个点$m$条边的联通无向图$G$(无自环),每条边都有一个颜色,选择其中任意多条边,使得$G$只通过这些边就能联通,且使得$L$最小,$L$表示这些边的颜色的集合的大小。

输入数据

第一行,两个正整数$n,m$,表示有$n$个点,$m$条边。

下面$m$行,每行三个正整数$a,b,c$表示一条边$<a,b>$颜色为$c$。

输出数据

第一行一个数$K$,表示你选出了$K$条边。

下面$K$行,每行一个数,表示你选择的边的序号。

输入样例

2 2
1 2 1
2 1 2

输出样例

1
1

数据范围

详见simplest1.in~simplest10.in

得分的计算方法:

假设你的答案为$out$,标程给出的答案为$std$。

那么所得到的分数$Score = \max(\lfloor 10(1 + \log_2\dfrac{std}{out}\rfloor, 1)$, 分数可以超过$10$分。

『湖南省队集训』planet

题目

也许一道题看上去很容易。。。。。。别大意

题目描述

众所周知,太阳只能照到农民星的一面,这让农民王很苦恼,毕竟农民是无法脱离阳光而独自存在的。不过最近,农民王有一件更加令他心烦的事情,他的老对手——反农联盟发射了一个干扰器到太空中去了,这个干扰器围着农民星旋转,而且同时在自转(围绕重心),这些旋转都是逆时针的。 任何时刻干扰器都不会和太阳或农民星相交。 为了简化问题,太阳视为一个点,农民星视为一个圆,而干扰器是一个简单多边形。问太阳在某个时刻能照射到的范围的长度。

输入数据

第一行,$X_s, Y_s, X_e, Y_e, R_e$,表示太阳的坐标$(X_s,Y_s)$, 农民星的坐标$(X_e,Y_e)$,$R_e$是农民星的半径。

第二行,$N,T_1,T_2,T$,表示干扰器有$N$个点,$T_1$是干扰器的公转周期,$T_2$是干扰器的自转周期,$T$是询问的时刻。

下面$N$行,每行两个数$x,y$,表示按顺序表示出干扰器的每个点。

输出数据

一个长度, 保留$2$位精度的小数,表示能照的弧长。

输入样例

-11 -6 9 7 9
7 100 120 95
-5 -3
-3 -4
-1 -3
-1 -2
-2 -1
-3 0
-4 -1

输出样例

13.45

数据范围

对于$30\%$的数据,$N \leq 10$;

对于$100\%$的数据,$N \leq 30$,输入文件中的所有数字均不超过$10000$且均为整数,$R_e, T, T_1, T_2$均大于$0$。

『湖南省队集训』clan

题目

最简单的往往最复杂

题目描述

有这么一个人叫做农民王Q,他有一个家谱,现在他在想自己和上古农民王U到底有多大的关系,关系式中有这么些个亲戚:

“father, mother, son, daughter, husband, wife, brother, sister, grandfather, grandmother, grandson, granddaughter, uncle, aunt, nephew, niece”

中文意思分别是:
“父亲,母亲,儿子,女儿,丈夫,妻子,兄弟,姐妹,爷爷,奶奶,孙子,孙女,叔叔,阿姨,侄儿,侄女”

对于亲戚关系,满足以下几点:

  1. Q的兄弟等同于Q的父亲的或者母亲的儿子(Q自己除外);
  2. Q的爷爷等同于Q的父亲的或者母亲的父亲;
  3. Q的孙子等同于Q的儿子的或者女儿的儿子;
  4. Q的叔叔等同于Q的父亲的或者母亲的兄弟;
  5. Q的侄儿等同于Q的兄弟的或者姐妹的儿子;
  6. 上述规则对于姐妹,奶奶,孙女,阿姨和侄女类似。

血缘关系的定义如下:

  1. Q到Q的父亲,Q的母亲,Q的儿子或者Q的女儿的距离为1;
  2. Q到Q的丈夫(妻子)的距离为0;
  3. Q到U的距离等于在上述规则下推断出的Q到U的最短距离。

由于一条关系会出现很多种情况,所以农民王想知道他跟上古农民王的血缘关系距离究竟有多少种?分别是多少?请你帮帮他好吗?

注明:不会出现的关系包括收养,亲戚间结婚(家族树中无环),离婚,复婚,重婚,同性恋等。

输入数据

第$1$行包括一个字符串表示氏族谱图上的关系式,格式如下:

Q is U’s relation’s relation’s … relation

设关系式中出现的亲戚关系总个数为$l$。

输出数据

第$1$行一个整数$c$,表示一共有多少种情况。

第$2$行$c$个数,表示每种情况的距离,空格隔开,按升序输出。

数据范围

对于$10\%$的数据,$l \leq 10$;

对于$30\%$的数据,$l \leq 30$;

对于另外$20\%$的数据, 只包含“父亲,母亲,儿子,女儿,丈夫,妻子,兄弟,姐妹”关系,且兄弟姐妹关系个数不超过$20$个;

对于$100\%$的数据,$0 \leq l \leq 100$,不保证一定存在一种情况满足关系式。

『湖南省队集训』string

题目

backgrounds

夕阳镇第五幼儿园的zhangzj是字符串之神,AC自动机、AK自动机、factor Oracle、后缀数组、后缀树、后缀自动机、后缀平衡树、后缀仙人掌、后缀平面图他都会,一天他在回家路上捡到了三个字符串,他发现这些字符串很好玩,于是他想通过其中两个字符串构成一个长字符串,用第三个字符串在其中匹配,但是他着急找他的好♂友玩(hei)(hei)(hei),只好请你来帮忙。

content

给定三个字符串$a,b,c$,它们的字符集均为小写字母,即{$a,b,c,\dots,z$}。

令$F_0=a,F_1=b,\dots,F_i=F_{i-1}+F_{i-2}(i \leq 2)$。

其中$+$表示字符串的连接。

现在有$q$个询问,每次询问给定$n,l,r,L,R$,求在$F_n$的第$l$个到第$r$个字符组成的字符串中,$s$的第$L$个字符到第$R$个字符组成的字符串的出现次数。

input format

第一行一个字符串$a$。

第二行一个字符串$b$。

第三行一个字符串$s$。

第四行一个正整数$q$。

下接$q$行,每行五个数:$n,l,r,L,R$,表示询问。

output format

共$q$行,每行对应一个询问的答案。

sample input

a
b
bb
4
4 1 5 1 2
4 1 1 1 2
4 2 4 1 1
6 1 13 1 2

sample output

1
0
2
3

sample explanation

$F_0 = “a”$;

$F_1 = “b”$;

$F_2 = “ba”$;

$F_3 = “bab”$;

$F_4 = “babba”$;

$F_5 = “babbabab”$;

$F_6 = “babbababbabba”$。

constraints

数据编号 数据范围 特殊条件
$1$ $|F_n|, |s|, q \leq 100$ $L = 1, R = |s|$
$2$ $|F_n|, |s|, q \leq 100$ $l = 1, r = |F_n|$
$3$ $|F_n|, |s|, q \leq 100$
$4$ $|F_n|, |s|, q \leq 1000$ $L = 1, R = |s|$
$5$ $|F_n|, |s|, q \leq 1000$ $l = 1, r = |F_n|$
$6$ $|F_n|, |s|, q \leq 1000$
$7$ $|s|, q \leq 1000$,$1 \leq |F_n| \leq 10^5$ $L = 1, R = |s|$,$l = 1, r = |F_n|$
$8$ $|s|, q \leq 1000$,$1 \leq |F_n| \leq 10^5$ $L = 1, R = |s|$
$9$ $|s|, q \leq 1000$,$1 \leq |F_n| \leq 10^5$ $l = 1, r = |F_n|$
$10$ $|s|, q \leq 1000$,$1 \leq |F_n| \leq 10^5$
$11$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$ $L = 1, R = |s|$,$l = 1, r = |F_n|$
$12$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$ $L = 1, R = |s|$,$l = 1, r = |F_n|$
$13$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$ $L = 1, R = |s|$
$14$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$ $L = 1, R = |s|$
$15$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$ $l = 1, r = |F_n|$
$16$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$ $l = 1, r = |F_n|$
$17$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$
$18$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$
$19$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$
$20$ $|s|, q \leq 10^4$,$1 \leq |F_n| \leq 10^9$

对于$100\%$的数据,$1 \leq |F_n| \leq 10^{9}$,$1 \leq l \leq r \leq |F_n|$,$1 \leq L \leq R \leq |s|$,$1 \leq |a|, |b|, |s| \leq 10^4$,$1 \leq q \leq 10^4$。

『湖南省队集训』game

题目

backgrounds

夕阳镇第五幼儿园的zhangzj被他的好♂友带进了puzzle game 的坑,其中他最感兴趣的是netgame,$1 \times 1$的格子他一眼秒,但由于幼儿园有上机时间限制,所以他想很快找出最优解,但是他忙着找更多的好♂友,只好请你来帮忙。

content

有一个$n \times m$的网格,除了最左边一列和最右边一列,每个格子上有一些管道,需要通过旋转一些格子使得最右边一列上的一些格子能够通过管道与至少一个最左边一列的格子连通。每个格子上的管道都是由一个中间管道扩展到四个方向中的若干个,也就是说,这个格子的四个方向上如果有管道,那么这些方向是联通的。例如上方、左方和右方有管道,那么这三个方向的格子如果有朝向这个格子的管道,就可以通过这个格子上的管道连通。

比如这样:



问最右边一列的格子最多有几个同时与最左边一列的格子连通。

input format

多组数据。

对于每组数据,第一行有两个整数$n$和$m$,为网格图的行数和列数。

下接$n$行,每行$m-2$个整数$x_{i,j}$,表示网格图第$i$行第$j+1$列的管道,如果$x_{i,j}\ {\rm and}\ 1 = 1$,那么向上有管道,如果$x_{i,j}\ {\rm and}\ 2 = 2$,那么向右有管道,如果$x_{i,j}\ {\rm and}\ 4 = 4$,那么向下有管道,如果$x_{i,j}\ {\rm and}\ 8 = 8$,那么向左有管道。

output format

若干行,每行一个数,表示一组数据的答案。

sample input

1 3
5

sample output

1

sample explanation

将中间的格子旋转成向左和向右连通即可。

constraints

对于$20\%$的数据,$n \times (m - 2) \leq 8$。

对于另外$10\%$的数据,$n = 1$。

对于另外$10\%$的数据,$m = 3$。

对于$100\%$的数据,$1 \leq n \leq 9$,$3 \leq m \leq 20$,数据组数在$5$以内。

数据有梯度,大家可以尽情骗分。

『湖南省队集训』graph

题目

backgrounds

夕阳镇第五幼儿园的zhangzj发现每个幼儿园的好♂友关系都会构成一个图,由于身处图中,zhangzj决定研究这些图,经过1s的思考,他发现这些图有很多种类型,于是他想知道每种类型的图有多少个,但是由于他只有十个手指头、十个脚趾头和一个脑袋,所以他数不过来,只好请你来帮忙。

content

图的定义:图$G$是一个有序二元组$(V,E)$,其中$V$称为点集,$E$称为边集,$E$与$V$不相交。它们亦可写成$(G)$和$E(G)$。

此题中图不允许有重边和自环。

树的定义:树是一种特殊的图,它是一个连通图,且任意删去一条边,它就不连通。

两个图同构的定义:

设这两个图为$G_1=(V_1,E_1)$,$G_2=(V_2,E_2)$:

  1. 点数相同。
  2. 如果是一个有标号的图,那么他们同构等价于$E_1=E_2$。
  3. 如果是一个无标号的图,且存在一种对于$G_1$和$G_2$的标号使得新的两个有标号图同构,那么它们同构。

问题描述:

  1. 给定一个整数$n$,求$n$个点的有标号的无根树的个数。
  2. 给定一个整数$n$,求$n$个点的有标号的有根树的个数。
  3. 给定一个整数$n$,求$n$个点的无标号的无根树的个数。
  4. 给定一个整数$n$,求$n$个点的无标号的有根树的个数。
  5. 给定一个整数$n$,求$n$个点的有标号的所有点的度数均为偶数的图的个数。
  6. 给定一个整数$n$,求$n$个点的有标号的欧拉图的个数。
  7. 给定一个整数$n$,求$n$个点的有标号的二分图的个数。

求方案数对$m$取模的结果。保证$m$是质数

input format

一行八个数$m,n_1,n_2,n_3,n_4,n_5,n_6,n_7$,分别为原问题中的$m$和七个问题的$n$。

output format

一行七个数,表示七个问题的答案。

sample input

5 2 2 2 2 2 2 2

sample output

1 2 1 1 1 0 2

constraints

对于$10\%$的数据,$n_1,n_2,n_3,n_4,n_5,n_6,n_7 \leq 5$。

对于$30\%$的数据,$n_1,n_2,n_5 \leq 1000$,$n_3,n_4,n_6,n_7 \leq 10$。

对于$50\%$的数据,$n_1,n_2 \leq 10^7$,$n_5 \leq 10^9$,$n_3,n_4,n_6,n_7 \leq 100$。

对于$100\%$的数据,$1 \leq n_1,n_2,n_5 \leq 10^{18}$,$n_3,n_4,n_6,n_7 \leq 1000$,$1 \leq m \leq 10^9$。

对于每个测试点,如果$7$个答案中有$4$个是对的,那么可以得到$1$分。如果有$6$个是对的,那么可以得到$2$分。如果有$7$个是对的,那么可以得到满分$5$分。

题解

有标号的无根树的个数

学过prufer序列的都知道答案是$n^{n - 2}$。注意不要爆long long,当然$n = 1$需要特判(虽然$1^{-1}=1$但你的快速幂求不出来啊)。

有标号的有根树的个数

无根树随便挑一个根就好了,不难证明这是不重不漏的。答案就是$n^{n - 1}$。

无标号的无根树的个数

在做之前,先假设我们会求无标号的有根树个数,至于怎么求等会再说。(嗯我就是故意按照题目顺序的)

先设由$n$个结点组成的无标号的有根树有$a_n$个。

直接做似乎不太好做,我们不妨换个角度,考虑容斥。我们只需要求出因重复而需要减去的有根树的个数即可。

在所有的有根树中,选取连接根结点和它的第一个儿子的一条边,它两端可以看做是两棵有根树连接上来的。那么,两端的树交换过来的话,仍然是一棵同构的无根树,因此枚举一端的树的大小,就得到如下的式子:

$$ans_n = a_n - \sum_{i = 1}^{\lfloor \frac{n}{2}\rfloor}a_ia_{n - i}$$

看起来做完了,但是如果$n$是偶数,可能会出现两棵树完全一样的情况,这相当于我们多减了,需要加回来。如果两棵树大小都是$\dfrac{n}{2}$,那么它们不同的情况只有$\dfrac{a_{\frac{n}{2}}(a_{\frac{n}{2}} - 1)}{2}$种,但我们减了$a_{\frac{n}{2}}^2$种,因此还要加回来$\dfrac{a_{\frac{n}{2}}(a_{\frac{n}{2}} + 1)}{2}$种。

说的有点乱,本质上就是枚举边两端的有根树大小,减去重复的,加上多减的,就完了。

无标号的有根树的个数

警告:公式恐惧症患者请连按几次PageDown键直接阅读结论。

既然是有根树,我们不妨枚举根的所有儿子,这样就可以通过小规模的问题来解决更大规模的问题。

为了方便,记$i$个结点构成的无编号的有根树有$a_i$个。

考虑大小为一定值的儿子的个数,不妨记以这些儿子为根的子树中,大小为$i$的有$c_i(\ge 0)$个,那么显然有

$$\sum_{i = 1}^{n - 1}ic_i = n - 1$$

对于每一种大小,显然它共有$a_i$种构造方法。在这$c_i$棵子树中,设采用第$j$种构造方法的有$x_{i,j}(\\ge 0)$种,那么

$$\sum_{j = 1}^{a_i}x_{i, j} = c_i$$

现在我们要求这个方程有多少组解。令$y_{i, j} = x_{i, j} + 1$,显然$y_i$的解与$x_i$的解是一一对应的,同时对于$y_i$有

$$\sum_{j = 1}^{a_i}y_{i, j} = c_i + a_i, y_{i, j} > 0$$

利用组合数学中的隔板法,不难得出解数为$C_{a_i + c_i - 1}^{a_i - 1}$,也就是$C_{a_i + c_i - 1}^{c_i}$。当然,不同的子树大小对应的方案数互补影响,可以利用乘法原理计算。因此,总结上面所说的内容,对于每一种划分方案${c}$,方案总数为

$$\prod_{i = 1}^{n - 1}C_{a_i + c_i - 1}^{c_i}$$

最后把所有的划分方案加起来,就是

$$a_n = \sum_{\sum_{i = 1}^{n - 1}(ic_i) = n - 1}\left (\prod_{i = 1}^{n - 1}C_{a_i + c_i - 1}^{c_i}\right)$$

这就可以递推了嘛!你要问复杂度?这取决于$\sum_{i = 1}^{n - 1}ic_i = n - 1$的解数,$n$比较小时并不是很大哦~

好了不开玩笑了,这东西怎么能跑过$n = 1000$呢。要优化这算法,我们还需要更先进的姿势。为了方便,设$a_0 = 0$。

考虑数列$\{a_n\}$的母函数

$$A(x) = \sum_{i = 0}^{+\infty}a_ix^i$$

我们想把它搞成一个好看的形式,也就是说我们要造一个有限项的函数,让它等价于这个东西。

先介绍一点基础知识,下面的组合学方法可以沟通有限和无限。组合数自古以来都是定义在非负整数集上的,因为负数的阶乘没有定义。但如果我们换一种计算方法,也就是这么算:

$$C_{n}^{m} = \frac{n!}{m!(n - m)!} = \frac{\prod_{i = n - m + 1}^{n}i}{\prod_{j = 1}^{m}j}$$

就是从$n$开始往下算“阶乘”,从$1$开始往上算“阶乘”,各算$m$次,相除便是答案。这样计算的话,对于$n$为负数的情况也可以兼容了,因此定义

$$C_{n}^{m} = \frac{\prod_{i = n - m + 1}^{n}i}{\prod_{j = 1}^{m}j}, n \in {\mathbb Z}, m \geq 0$$

我们不妨试试,如果$n$为负数会算出来什么。经过一番整理,其实就是

$$C_{n}^{m} = \frac{\prod_{i = n - m + 1}^{n}i}{\prod_{j = 1}^{m}j} = \frac{\prod_{i = -n}^{-n + m - 1}(-i)}{\prod_{j = 1}^{m}j} = (-1)^m\frac{\prod_{i = -n}^{-n + m - 1}i}{\prod_{j = 1}^{m}j} = (-1)^mC_{-n + m - 1}^{m}, n < 0, m \geq 0$$

这样我们就会算推广的组合数了。不难发现,因为定义的等价性,二项式定理似乎也可以推广,也就是

$$(1 + x)^{n} = \sum_{k = 0}^{+\infty}C_{n}^{k}x^k = \sum_{k = 0}^{+\infty}(-1)^kC_{-n + k - 1}^{k}x^k, n < 0$$

好吧以上东西都是为了方便理解瞎BB的,但是这个式子是正确的。这一步非常关键,因为它把一个分式和一个无穷级数画上了等号。如果把$n = -1$带入,那么就是

$$(1 + x)^{-1} = \sum_{k = 0}^{+\infty}(-1)^kC_{k}^{k}x^k = \sum_{k = 0}^{+\infty}(-x)^k$$

这是显然正确的,运用等比数列求和即可证明。

然后问题就是找到一个分式满足展开后的形式满足$\{a_n\}$的递推式。这是很困难的,还好有前人已经找出来了。

首先我们有如下式子:

$$(1 - x^r)^a = \sum_{k = 0}^{+\infty}C_{-a + k - 1}^{k}x^{rk}, a < 0$$

考虑计算

$$\prod_{i = 1}^{+\infty}(1 - x^i)^{-a_i}$$

的展开式中$x^n$项的系数,我们可以枚举这$n$个$x$分别来自于哪一项,这里就和上面分析子树的那一段一模一样了。最后的结果我们也很熟悉,就是

$$\sum_{\sum_{i = 1}^{n}(ic_i) = n}\left (\prod_{i = 1}^{n}C_{a_i + c_i - 1}^{c_i}\right)$$

它恰好等于$a_{n + 1}$,为了满足生成函数的性质,我们把它乘上一个$x$,就得到生成函数$A$了:

$$A(x) = \frac{x}{\prod_{i = 1}^{+\infty}(1 - x^i)^{a_i}}$$

然而这并没有卵用,毕竟右面还是有无限项,不要慌嘛。我们把两边都取个对数看看:

$$\ln A(x) = \ln x - \sum_{i = 1}^{+\infty}a_i\ln(1 - x^i)
= \ln x + \sum_{i = 1}^{+\infty}a_i\ln(\frac{1}{1 - x^i})$$

注意到右面有出现了分式,还是在对数里面,我们考虑积分相关的知识。为了方便,这里直接把$x^i$作为积分变量,设$t = x^i$,那么由于$(\ln\dfrac{1}{1 - t})‘ = \dfrac{1}{1 - t}$,所以$\int\dfrac{1}{1 - t}dt = \ln\dfrac{1}{1 - t}$,所以

$$\ln\frac{1}{1 - t} = \int\frac{1}{1 - t}dt = \int\sum_{k = 0}^{+\infty}t^k = \sum_{k = 1}^{+\infty}\frac{1}{k}t^{k}$$

带回上式就是

$$\ln A(x) = \ln x + \sum_{i = 1}^{+\infty}\left(a_i\sum_{k = 1}^{+\infty}\frac{1}{k}x^{ik}\right)$$

交换一下求和符号,就是

$$\ln A(x) = \ln x + \sum_{k = 1}^{+\infty}\left(\frac{\sum_{i = 1}^{+\infty}a_ix^{ik}}{k}\right)$$

根据生成函数的定义,可以化为

$$\ln A(x) = \ln x + \sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)$$

这已经很漂亮了,我们考虑两边再取一下指数。为了方便,定义$\exp(x) = e^x$:

$$A(x) = x\exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)$$

然后对两边求导得到

$$A’(x) = \exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right) + x\exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)‘$$

又因为

$$\frac{A(x)}{x} = \exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)$$

所以

$$A’(x) = \frac{A(x)}{x} + A(x)\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)‘$$

把右面的那一坨东西用一下求导公式,就成了

$$\frac{dA(x)}{d(x)} = \frac{A(x)}{x} + A(x)\left(\sum_{k = 1}^{+\infty}\left( x^{k - 1}\frac{dA(x^k)}{d(x^k)}\right)\right)$$

$$\frac{dA(x)}{d(x)} - \frac{A(x)}{x} = A(x)\left(\sum_{k = 1}^{+\infty}\left( x^{k - 1}\frac{dA(x^k)}{d(x^k)}\right)\right)$$

根据多项式求导的计算方法,我们可以展开成这样:

$$\sum_{i = 0}^{+\infty}(i + 1)a_{i + 1}x^i - \sum_{i = 0}^{+\infty}a_{i + 1}x^i = \left(\sum_{i = 0}^{+\infty}a_{i}x^i\right)\left(\sum_{k = 1}^{+\infty}\left( x^{k - 1}\sum_{j = 1}^{+\infty}ja_jx^{k(j - 1)}\right)\right)$$

稍微变形一下就是

$$\sum_{i = 0}^{+\infty}ia_{i + 1}x^i = \left(\sum_{i = 0}^{+\infty}a_{i}x^i\right)\left(\sum_{j = 1}^{+\infty}\left( ja_j\sum_{k = 1}^{+\infty}x^{jk - 1}\right)\right)$$

现在我们只考虑$a_{n + 1}$。显然还需要枚举一下不同的$j$,假设确定了$j$,那么对于每一个合法的$k$,对应的$i$也是唯一确定的,所以我们有

$$na_{n + 1} = \sum_{j = 1}^{n}ja_j\sum_{k = 1}^{\lfloor \frac{n}{j} \rfloor}a_{n + 1 - jk}$$

也就是

$$a_{n + 1} = \frac{1}{n}\sum_{j = 1}^{n}ja_j\sum_{k = 1}^{\lfloor \frac{n}{j} \rfloor}a_{n + 1 - jk}$$

这样的递推关系就很显然了嘛!只需要枚举$j, k$就好了。

待续。。。。。。

,