FPS 24: 24 Problems on Formal Power Series

FPS 24: 24 Problems on Formal Power Series

A - Snack

$[x^n](x+x^3+x^4+x^6{)}^d$

B - Tuple of Integers

组合意义等价于 $x+y=n$ 的方案数，$n+1$。

C - Sequence

$[x^s](1+\dots +x^m{)}^n$

D - Sequence 2

枚举中间间隔长度。

${\sum }_i(m-n-i+1)[x^i](1+x^2+\dots {)}^{n-1}$

E - Sequence 3

直接背包。

F - Colored Paper

直接矩阵快速幂。

G - Coin

直接背包、退背包。

H - Jump

枚举有 $i$ 个额外的 $(0,b)$，且 $n$ 次 $(1,b)$ 共向上 $j$。

$\sum \left(\genfrac{}{}{0ex}{}{n+i}{n}\right)\left(\genfrac{}{}{0ex}{}{j+n-1}{n-1}\right)\left(\genfrac{}{}{0ex}{}{m-j-1}{i-1}\right)$

I - Score

$[x^k]\prod (1+a_{i}x)$

J - Sugoroku

$f_i=\sum f_j{a}_{i-j}$

K - Permutation

容斥 $k$ 个爆掉，$(-1{)}^k$。每拼上一段乘 $(-1)len!$。

$f_i=\sum -f_j(i-j)!$

L - Permutation 2

长为 $l$ 的置换环方案数 $(l-1)!$，exp 起来。

$n![x^n]exp(\sum \frac{(i-1)!x^i}{i!})$

M - Connected Graph

here

$f_i=2^{\frac{i(i-1)}{2}}\sum \left(\genfrac{}{}{0ex}{}{i-1}{j-1}\right)f_j{2}^{\frac{(i-j)(i-j-1)}{2}}$

N - Coin 2

$[x^n]\prod \frac{1-x^{i(a_i+1)}}{1-x^i}$

先 ln 再 exp。$ln(1-x)={\sum }_{i\le 1}-\frac{x^i}{i}$。

O - Rooted Tree

方案数是 $\frac{(n-2)!}{\prod (d_i-1)!}$。特判根节点度数。

$(n-2)!}{x}^p)(x+{\sum }_p\frac{1}{p!}{x}^{p+1}{)}^{n-1}$