欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-05 15:40:31
题面 "题目链接" Sol 生成函数入门题 至多为$k$就是$\frac{1 x^{k+1}}{1 x}$ $k$的倍数就是$\frac{1}{1 x^k}$ 化简完了就只剩下一个$\frac{1}{(1 x)^5}$ 这个东西可以直接广义二项式定理展开,也就是这个式子 $$\frac{1}{(1 ......

题面

题目链接

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))