Atcoder FPS 24 记录

awa
A
记 \(f_{i,j}\) 表示前 \(i\) 天花了 \(j\) 块的方案，有转移 \(f_{i,j}=f_{i-1,j-1}+f_{i-1,j-3}+f_{i-1,j-4}+f_{i-1,j-6}\)，边界是 \(f_{0,0}=1\)。
把 \(f_i\) 的生成函数写出来，也就是 \(F_i(x)=\sum\limits_{j=0}^{n}f_{i,j}x^j\)，可以发现 \(f_i=f_{i-1}\times(x+x^3+x^4+x^6)=(x+x^3+x^4+x^6)^i\)，答案就是 \((x+x^3+x^4+x^6)^d\) 的 \(n\) 此项系数。
直接把多项式快速幂写上去会 T 掉，可以发现 \(x+x^3+x^4+x^6=x(1+x^2)(1+x^3)\)，用二项式定理拆一下，然后做一遍 NTT 就行。