题目是我们上一届 队长ZZY出的如下：
E :ZZY的宠物
描述
ZZY领养了一对刚刚出生的不知名小宠物..巨萌巨可爱!!...小宠物的生命为5个单位时间并且不会在中间出意外翘辫子(如:
从0出生能活到5但活不到6)..小宠物经过2个单位时间成熟..刚刚成熟的一对小宠物能立即生育6只新的小宠物(如:
从0出生的一对在2时成熟并进行第一次生育）...小宠物是很忠诚的..不会在中途换伴侣..每对小宠物生育一次这一对的生育能力就会降低2个..也就是说一对小宠物在第二次生育时就只能生4个了..小宠物成熟后每个单位时间都会尽力的生育(例:
从0出生的一对..2时间生6个..3时间生4个..4时间生2个...5时间生不出..6时间这一对已经挂了..)..生育出来的新小宠物会继续这个过程..
ZZY想知道从单位时间0开始..经过M个单位时间(时间为M时)将有多少只活着的小宠物(0时刻有2只小宠物)
因为ZZY隐隐地觉得什么地方怪怪的...所以请将这个数目mod 10000
输入
多组数据读到EOF
每组数据一行:
M ( 0<=M<=2000000000 )
最多500组数据
输出
每组输出一行为 Case
组号: 答案，即M时刻活着的小宠物个数%10000
样例输入
0
1
2
3
4
8
样例输出
Case 1: 2
Case 2: 2
Case 3: 8
Case 4: 12
Case 5: 32
Case 6: 528
这题我已经完全把它转化为我自己的东西了，看了队长ZZY的博客很久。
我刚刚作出来了，最兴奋的是还在队长的基础上改良了一点，虽然这不算什么，但我还是很高兴
队长使用了k=6来循环来加得最终的sum结果，其实只要把那一列或一行相加就行了（至于是列还是行，具体要看你的关系矩阵了）
首先我们可以用数组表示处于某一时间的宠物的个数（如s[6][6]）（我们只用第一行来表示就可以了）（s[0][i]表示处于时间i宠物的个数）
时间 s[0][0] s[0][1] s[0][2] s[0][3] s[0][4] s[0][5]
0 2 0 0 0 0 0
1 0 2 0 0 0 0
2 6 0 2 0 0 0
3 4 6 0 2 0 0
4 18+2 4 6 0 2 0等等
我们可以发现：除了s[0][0]是要通过某种计算得到，其他的像s[0][1],s[0][2]啊 都是上个时间s[0][0],s[0][1]向右平移一位得来的
根据题意我们应该可以得到i时间的s[0][0]=(i-1时间中的）s[0][1]*3+s[0][2]*2+s[0][3]*1. （关系式 1）
用矩阵模拟一下就出来了：
初始矩阵A:2 0 0 0 0 0 想要变成时间为1的状态矩阵（0 2 0 0 0 0 即使第一行向右平移下，根据矩阵乘法的定义 逆推一下就可以确定
0 0 0 0 0 0 0 0 0 0 0 0 关系矩阵B（0 1 0 0 0 0 中1的位置，在把关系式 1嵌入到矩阵乘法中
0 0 0 0 0 0 0 0 0 0 0 0 3 0 1 0 0 0 就得到左边的关系矩阵了!
0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0) 0 0 0 0 0 1
0 0 0 0 0 0）
然后用快速幂计算A*B^m(m为时间) 将第一行相加 就得到结果了
注意要%10000哦。
代码如下：
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
struct maxtrix
{
int s[6][6];
}h,n,p,q;
maxtrix cheng(maxtrix a,maxtrix b)
{
int i,k,j;
maxtrix h;
memset(h.s,0,sizeof(h.s));
for(k=0;k<6;k++)
for(j=0;j<6;j++)
for(i=0;i<6;i++)
h.s[i][j]=(h.s[i][j]+a.s[i][k]*b.s[k][j])%10000;
return h;
}
maxtrix ksmi(maxtrix a,int b)
{
if(b==0)return q;
if(b==1)return n;
maxtrix ff;
ff=ksmi(a,b/2);
ff=cheng(ff,ff);
if(b%2==0)return ff;
else return cheng(ff,a);
}
int main()
{
int a,b,c,nn=0;
while(cin>>a)
{
nn++;
c=0;
maxtrix uu;
memset(n.s,0,sizeof(n.s));
n.s[0][1]=n.s[1][2]=n.s[2][3]=n.s[3][4]=n.s[4][5]=1;
n.s[1][0]=3;n.s[2][0]=2;n.s[3][0]=1;
memset(p.s,0,sizeof(p.s));
p.s[0][0]=2;
memset(q.s,0,sizeof(q.s));
q.s[0][0]=1;
uu=ksmi(n,a);
uu=cheng(p,uu);
//cout<<uu.s[0][0]<<" "<<uu.s[0][1]<<" "<<uu.s[0][2]<<" "<<uu.s[0][3]<<" "<<uu.s[0][4]<<" "<<uu.s[0][5]<<endl;
for(b=0;b<6;b++)
c=(c+uu.s[0][b])%10000;
cout<<"Case "<<nn<<": ";
cout<<c<<endl;
}
return 0;
}