Score

0+30+15=450 + 30 + 15 = 45

rank 28

Process

玩了一早上T1,然后花了点时间想T3,但是没有想到容斥导致无法推出任何有用的信息,T2最后看了看想了个做法但没时间写了 (实际上就是正解)

Problem

林海的密码 (password)

C=13C = 13 为例:

20-7-19-1

考虑 SS 选谁为父亲,若选 aa,则有 232^3 种方案; 若选 bb,则有 222^2 种方案; 若选 dd,则有 202^0种方案

加起来即为 1313

code

皮卡丘 (pikachu)

由于S,T105\sum |S|, \sum T \le 10^5,考虑直接用Trie树维护: 操作1直接在根打标记; 操作2暴力在Trie上走、新开点、删点

总共需要维护三个信息: sum,nxt,tagsum, nxt, tag 分别表示子树内总点数、子树内下一步会新增的点数、子树内还需要经过的轮数

code

我永远喜欢 (always)

先不管环,考虑序列上如何做

f(a,b)f(a, b) 表示把 aa 个相同颜色的球分成 bb 段的贡献之和。考虑枚举一个序列 表示每段的长度,则有:

f(a,b)=t=a1i=1bti! f (a, b) = \sum_{\sum_{t} = a} \frac{1}{\prod_{i=1}^{b} t_i!}

转化成生成函数的形式:

f(a,b)=[xa](ex1)b=[xa]i=0b(bi)(1)biexi=i=0b(bi)(1)biiaa! \begin{aligned} f (a, b) &= [x^a] (e^x - 1)^{b} \\ &= [x^a] \sum_{i=0}^{b} {b \choose i} (-1)^{b - i} e^{xi}\\ &= \sum_{i=0}^{b} {b \choose i} (-1)^{b - i} \frac{i^a}{a!} \end{aligned}

可以卷,不管了

考虑枚举一个数组 bib_i 表示第 ii 种颜色的球被分成了 bib_i段,则每种方案的贡献和为 i=1nf(ai,bi)\sum_{i=1}^{n} f(a_i, b_i)。但我们无法直接求出方案数,因为这些段组合起来后,某些段可能会合并成一个大段。考虑从这个限制出发容斥:

再枚举一个数组 cic_i 表示第 ii 种颜色合并了 cic_i 次,容斥系数为 (1)ci(-1)^{\sum c_i}

ans=bc(bici)!(bici)!(1)cii=1nf(ai,bi)(bi1ci) ans = \sum_{b} \sum_{c} \frac{(\sum b_i - c_i)!}{\prod (b_i - c_i)!} (-1)^{\sum c_i} \prod_{i=1}^{n} f(a_i, b_i) {b_i - 1 \choose c_i}

可以把容斥系数放到里面,再把bicib_i - c_icic_i交换一下:

ans=bc(ci)!ci!i=1nf(ai,bi)(bi1ci1)(1)bici ans = \sum_{b} \sum_{c} \frac{(\sum c_i)!}{\prod c_i!} \prod_{i=1}^{n} f(a_i, b_i) {b_i - 1 \choose c_i - 1} (-1)^{b_i - c_i}

然后不想写了,贴一下网上的

20-7-19-2

另外还有一个很玄学牛逼不知道怎么证明的结论:

20-7-19-3

code