upd 2022-01-26 我找到了个题集
牛客竞赛数学专题班生成函数I（线性递推关系、生成函数概念与公式推导、暴力计算）
目录
题目链接
题面
解题思路
AC代码
题目链接
https://ac.nowcoder.com/acm/contest/10322/C
题面
自助餐厅里有5个盘子，里面装的都是面包。
第1个盘子里有无限个面包；
第2个盘子里只有1个面包；
第3个盘子里只有4个面包；
第4个盘子里也有无限个面包，但必须两个两个地拿；
第5个盘子里也有无限个面包，但必须5个5个地拿；
给定正整数n，求有多少种正好拿出n个面包的方案。
方案a和方案b不同，当且仅当方案a存在从某个盘子里拿出面包的数量与方案b中对应盘子拿出的数量不同。
n<=10^9
数据仅包含一个正整数n
输出一个正整数表示答案。
解题思路
这一眼看过去就是OGF板子题
或者让现在的我来看，就是5个序列做卷积
\[\frac{1}{1-x}(1+x)(1+x+x^2+x^3+x^4)\frac{1}{1-x^2}\frac{1}{1-x^5}
\]
结果扔到mma里给我算出来这玩意？？
我临时找到一种办法
标答给的是\((n+1)(n+2)/2\)，最后可以化简成这样，考试的时候没想起来
\[\sum_{n=0}^{\infty}\binom{n+2}{2}x^n=1/(1-x)^3
\]
做这题给我的教训是记得用FullSimply能化简先化简一下
嗯复杂度看起来过不去，可能数据出的水就过了？
AC代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型
* @return long长整型
*/
long long wwork(int n) {
// write code here
long long ans=0;
for(long long i=0;i<=n;i++){
if((n-i)%5==0){
if(i>=2)
ans+=(5*i-5);
else if(i==0)
ans+=1;
else if(i==1)
ans+=3;
else if(i==2)
ans+=6;
}
}
return ans;
}
};
