首页 > 代码库 > XJOI1680阿猫的实验

XJOI1680阿猫的实验

阿猫的实验

阿猫很喜欢生物学。他还在今年的全国中学生生物学联赛中获得了一等奖。
一天,阿猫在实验室听说了这样一种繁殖能力很强的老鼠。
这种老鼠在出生后的第一个月,可以生出a 对老鼠;第二个月,可以生出b 对老鼠;第三个
月及以后的每个月,都可以生出c 对老鼠。
阿猫对此十分好奇。他很想知道,如果他有一对刚出生的老鼠,按最理想的模式繁殖,且老
鼠不死,那么最少需要多少个月它们就可以覆盖整个地球。
为了完成这一猜想,阿猫需要知道这种老鼠在第N 个月时的数量。

输入格式:

输入只有一行,四个数,分别为a,b,c,N(0<=a<=b<=c<=100,N<=3000),
其含义为题目所述。

输出格式:

输出只有一个数,为第N 个月老鼠的数量。

样例输入:

0 1 1 11

样例输出:

144

高精度,很大的数,注意长度与进位的处理。(码农题)
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int a0[30001],a1[30001],a2[30001],a3[30001],s0,s1,s2,s3;
 6 int main()
 7 {
 8     int n,a,b,c;
 9     s1=s2=s3=0;
10     scanf("%d%d%d%d",&a,&b,&c,&n);
11     a0[1]=1;
12     s0=1;
13     for(int l=1;l<=n;l++)
14     {
15         s3=max(s2,s3);
16         for(int i=1;i<=s3;i++)
17         {
18             a3[i]+=a2[i];
19             if(a3[i]>=10)
20             {
21                 a3[i]-=10;
22                 a3[i+1]+=1;
23             }
24         }
25         if(a3[s3+1]>0) s3++;
26         memset(a2,0,sizeof(a2));
27         for(int i=1;i<=s1;i++) a2[i]=a1[i];
28         s2=s1;
29         memset(a1,0,sizeof(a1));
30         for(int i=1;i<=s0;i++) a1[i]=a0[i];
31         s1=s0;
32         memset(a0,0,sizeof(a0));
33         for(int i=1;i<=s1;i++)
34         {
35             a0[i]+=a1[i]*a;
36             a0[i+1]+=a0[i]/10;
37             a0[i]%=10;
38         }
39         for(int i=1;i<=s2;i++)
40         {
41             a0[i]+=a2[i]*b;
42             a0[i+1]+=a0[i]/10;
43             a0[i]%=10;
44         }
45         for(int i=1;i<=s3;i++)
46         {
47             a0[i]+=a3[i]*c;
48             a0[i+1]+=a0[i]/10;
49             a0[i]%=10;
50         }
51         s0+=50;
52         while(a0[s0]==0) s0--;
53         for(int i=1;i<=s0+10;i++)
54         {
55             a0[i+1]+=a0[i]/10;
56             a0[i]%=10;
57         }
58         s0+=20;
59         while(a0[s0]==0) s0--;
60     }
61     for(int i=1;i<=30000;i++)
62     {
63         a3[i]+=a2[i]+a1[i]+a0[i];
64         a3[i+1]+=a3[i]/10;
65         a3[i]%=10;
66     }
67     s3=30000;
68     while(a3[s3]==0) s3--;
69     for(int i=s3;i>=1;i--) printf("%d",a3[i]);
70     printf("\n");
71     return 0;
72 }

 

 

XJOI1680阿猫的实验