小O->机房的蚂蚱

前几天参加了BeyondLimits大佬的毕业邀请赛被虐的无地自容
现在准备水一篇题解,好了进入正题
题目大概是这么说的:有一天小机房里进了一只蚂蚱这种蚂蚱无性繁殖,并且繁殖能力很强。一只成年蚂蚱在x个月后开始产卵,且之后的每个月都产卵,成虫的产卵量为y。
卵在孵化两个月后变成成虫,这新孵化的成虫在第一个月不产卵,也就是说它还是是个孩子它在发育x+1个月后才开始产卵。
那吗问题来了求z个月后有多少只成虫
输入共一行三个正整数x,y,z
输出z个月后成虫的数量(数据很大要对1000008取模)
em无从下手那就递推吧,但是我就莫名其妙的冒出一种神奇的想法…那我们先推一组数据吧x=3 y=6 z=8
月 卵一个月 卵两个月 不产卵成虫 成虫一个月 成虫两个月 成虫三个月
1   0     0      0       1      0       0
2   0     0      0       0      1       0
3   6     0      0       0      0       1
4   6     6      0       0      0       1
5   6     6      6       0      0       1
6   6     6      6       6      0       1
7   6     6      6       6      6       1
8   42    6      6        6      6       7
歪七扭八我也不知道怎么调
那么我们可以发现每过一个月所有的数据往后推一位,最后一位和之前叠加,新的最后一位*产卵数就是新产卵的个数
最后把除了卵的全加起来就是答案,我们可以用数组把各种个数存起来,直接上代码 #include
#define MOD 1000008
int a[30];
int main()
{
int x,y,z;
scanf(“%d%d%d”,&x,&y,&z);
a[4]=1;//第一个月就这样从第二个月开始循环
for(int i=2;i<=z;i++) { a[x+3]+=a[x+2];a[x+3]%=MOD; for(int i=x+2;i>1;i–)
a[i]=a[i-1];
a[1]=a[x+3]*y%MOD;
}
int sum=0;
for(int i=3;i<=x+3;i++) sum+=a[i],sum%=MOD; printf(“%d\n”,sum); return 0; }
!但是我们发现这个算法时间复杂度大概是O(n^2)不要嘤嘤嘤
我们上面的算法是让1~x+2数组往后移一位,而最后一位不动。所以用相对运动的观点来看>_<我也不知道我砸想出来的就相当于数组不动,最后一位在向前移动,每次产卵虫的位置向前移动与前一位的个数叠加,产卵虫原来的位置变成新产的卵,最后求答案的时候不加两个卵的数量就ojbk了。qwq你们肯定听懂了;
上代码
#include
#define MOD 1000008
int a[30];
int main()
{
int x,y,z;
scanf(“%d%d%d”,&x,&y,&z);
a[4]=1;int k1=x+3,k2;
//k1为成虫,k2为刚产的卵
for(int i=2;i<=z;i++) { if(!–k1)k1=x+3,k2=1; else k2=k1+1; a[k1]+=a[k2],a[k1]%=MOD; a[k2]=a[k1]*y%MOD; } int sum=0; for(int i=1;i<=x+3;i++) if(i!=k2&&(k2!=x+3&&i!=k2+1||k2==x+3&&i!=1)) sum+=a[i],sum%=MOD; printf(“%d\n”,sum); return 0; } 对于边界的处理看代码吧,em这就快了很多嘤为不用移动数组了;