洛谷P2000 拯救世界(生成函数)

题面

题目链接

Sol

生成函数入门题

至多为(k)就是(frac{1-x^{k+1}}{1-x})

(k)的倍数就是(frac{1}{1-x^k})

化简完了就只剩下一个(frac{1}{(1-x)^5})

这个东西可以直接广义二项式定理展开，也就是这个式子

[frac{1}{(1-x)^n} = sum_{k=0}^{infty} C_{n+k-1}^{k-1}x^k ]

然鹅一开始我并不知道这个东西，然后就zz的对(frac{1}{(1-x)})求了四次导。

最后的答案也是((N+1)(N+2)(N+3)(N+4) / 24)

N = int(input())
print(int((N + 1) * (N + 2) * (N + 3) * (N + 4) / 24))