设F(n)F(n)F(n)为第nnn个月时，成虫的对数 面对这样经典的递推题，还是尝试寻找递推关系 可以注意到：F(n)F(n)F(n)实际上受两个因素影响： 1. 当月会有新成熟的成虫 2. 当月会有从上个月活下来的“老成虫” 可以注意到，当月新成熟的成虫一定是从前n−x−2n-x-2n−x−2个月的成虫产生的，每对成虫可以产生yyy对卵，则当月新成熟的成虫的个数为F(n−x−2)∗yF(n-x-2)*yF(n−x−2)∗y “老成虫”的数量显然为F(n−1)F(n-1)F(n−1) 故得，递推关系为：F(n)=F(n−x−2)∗y+F(n−1)F(n) = F(n-x-2)*y+F(n-1)F(n)=F(n−x−2)∗y+F(n−1) 由于初始的成虫的y对卵，在1+x1+x1+x个月后才能成熟，在此之前，F(n)=1F(n) = 1F(n)=1 故得，初始条件为：F(n)=1,n<=2+xF(n) = 1,n<=2+xF(n)=1,n<=2+x 总结： {F(n)=y∗F(n−x−2)+F(n−1),n>x+2F(n)=1,n≤x+2\begin{cases} F(n) = y*F(n-x-2)+F(n-1),n>x+2\\ F(n) = 1,n\leq x+2 \end{cases} {F(n)=y∗F(n−x−2)+F(n−1),n>x+2F(n)=1,n≤x+2 WARNING！！！ 题目求的是zzz个月后，由于我们是从第一个月出发，所以求的是F(z+1)F(z+1)F(z+1)而不是F(z)F(z)F(z)哦

#include<bits/stdc++.h> using namespace std; int main(){ int x, y, z; cin >> x >> y >> z; long long a[55] = {}, b[55] = {}; for(int i = 1; i <= x; i++) a[i] = 1; for(int i = x + 1; i <= z + 1; i++) { a[i] = a[i - 1] + b[i - 2]; b[i] = a[i - x] * y; } cout << a[z + 1]; return 0; }

#include<bits/stdc++.h> using namespace std; int x,y,z; long long cc[500000],luan[500000]; long long g(int n); long long f(int n); long long g(int n){ if(n<=x) return luan[n]; return luan[n]=f(n-x)*y; } long long f(int n){ if(cc[n]) return cc[n]; return cc[n]=f(n-1)+g(n-2); } int main(){ cin>>x>>y>>z; for(int i=1;i<=x;i++) cc[i]=1; cout<<f(z+1); return 0; }