湘潭校赛 Easy Wuxing

Easy Wuxing
Accepted : 25		Submit : 124
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述 “五行”是中国传统哲学思想，它认为认为大自然的现象由“木、火、土、金、水”这五种气的变化所总括， 不但影响到人的命运，同时也使宇宙万物循环不已。 五行具有相生相克的性质，规律如下： 五行相克：金克木，木克土，土克水，水克火，火克金。 五行相生：金生水，水生木，木生火，火生土，土生金。 五行任一行与其他五行的关系为：同我、生我、我生、克我、我克。 给你一个1*n的格子，将五行填上去，每格填一个，要求相邻格以及首尾格不能是同我和相克的关系， 请问一共有多少种不同的方案？ 输入 多组样例，每组一个整数n(0≤n≤10)，如果n为0，表示输入结束，这个样例不需要处理。 输出 每行输出一个样例的结果，因为数值可能非常大，请将结果对10+7取模。 样例输入 1 2 0 样例输出 5 10 Source XTU OnlineJudge

[ Submit Solution
]

 

 

矩阵快速幂取模

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 #include<queue>

 using namespace std;

 typedef __int64 LL;

 const LL mod = ;

 struct Matrix

 {

     LL mat[][];

     void Init()

     {

         LL cur;

         int i,j;

         mat[][]=;mat[][]=;mat[][]=;mat[][]=;mat[][]=;

         for(i=;i<=;i++)

         {

             for(j=;j<=;j++)

             {

                 if(j==) cur=;

                 else cur=j-;

                 mat[i][j]=mat[i-][cur];

             }

         }

     }

 }M_hxl;

 void Matrix_ini(Matrix *cur,int n)

 {

     int i,j;

     for(i=;i<=n;i++)

         for(j=;j<=n;j++)

             if(i==j)

                 cur->mat[i][j]=;

             else cur->mat[i][j]=;

 }

 Matrix Multiply(Matrix cur,Matrix now,int len)

 {

     Matrix ww;

     int i,j,k;

     memset(ww.mat,,sizeof(ww.mat));

     for(i=;i<=len;i++)

     for(k=;k<=len;k++)

     if(cur.mat[i][k])

     {

         for(j=;j<=len;j++)

         if(now.mat[k][j])

         {

             ww.mat[i][j]+=cur.mat[i][k]*now.mat[k][j];

             if(ww.mat[i][j]>=mod)

             ww.mat[i][j]%=mod;

         }

     }

     return ww;

 }

 struct Matrix M_add(Matrix cur,Matrix now,int len)

 {

     Matrix ww;

     int i,j;

     memset(ww.mat,,sizeof(ww.mat));

     for(i=;i<=len;i++)

     for(j=;j<=len;j++)

     {

         ww.mat[i][j]=cur.mat[i][j]+now.mat[i][j];

         if(ww.mat[i][j]>=mod)

         ww.mat[i][j]%=mod;

     }

     return ww;

 }

 Matrix pow_sum1(Matrix cur,int n,int len)

 {

     Matrix ww;

     Matrix_ini(&ww,len);

     while(n)

     {

         if(n&)

         {

             ww=Multiply(ww,cur,len);

         }

         n=n>>;

         cur=Multiply(cur,cur,len);

     }

     return ww;

 }

 void solve(int n)

 {

     LL k=;

     M_hxl.Init();

     M_hxl=pow_sum1(M_hxl,n,);

     k=(M_hxl.mat[][]+M_hxl.mat[][])%mod;

     k=(k*)%mod;

     printf("%I64d\n",k);

 }

 int main()

 {

     LL T,n;

     while(scanf("%I64d",&n)>)

     {

         if(n==)break;

         if(n==)

         {

             printf("5\n");

             continue;

         }

         solve(n-);

     }

     return ;

 }