题解：AT_fps_24_b 整数の組

生成函数好题。赛时通过观察样例秒掉了，赛后才证出来。

先说结论：答案是

N+1

。

证明

求

a,b,c,d

的母函数，则

A(x)=x+1

B(x)=x^2+x+1

C(x)=\sum_{i=0}^{\infin}(x^2)^i=\frac{1}{1-x^2}

D(x)=\sum_{i=0}^{\infin}(x^3)^i=\frac{1}{1-x^3}

求

a+b+c+d

的母函数，即求上述母函数的积，即

\begin{aligned} F(x)=&A(x)B(x)C(x)D(x)\\ =&(x+1)(x^2+x+1)\frac{1}{1-x^2}\cdot\frac{1}{1-x^3}\\ =&(x+1)(x^2+x+1)\frac{1}{(1+x)(1-x)}\cdot\frac{(x^2+x+1)}{(1-x)}\\ =&\frac{1}{(1-x)^2} \end{aligned}

所以答案是

[x^N]\frac{1}{(1-x)^2}

，但是还可以继续化简：~~众所周知~~我们有

[x^N]\frac{1}{(1-x)^r}={n+r-1\choose r-1}

，带入

r=2

得

[x^N]\frac{1}{(1-x)^2}={N+1\choose 1}=N+1

。

代码：没有代码，别忘了取模就行。

文章操作