湘潭校赛 Hard Wuxing

Hard Wuxing
Accepted : 13		Submit : 166
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述

“五行”是中国传统哲学思想，它认为认为大自然的现象由“木、火、土、金、水”这五种气的变化所总括，不但影响到人的命运，同时也使宇宙万物循环不已。五行具有相生相克的性质，规律如下：

五行相克：金克木，木克土，土克水，水克火，火克金。
五行相生：金生水，水生木，木生火，火生土，土生金。
五行任一行与其他五行的关系为：同我、生我、我生、克我、我克。

湘潭校赛 Hard Wuxing-LMLPHP
给你一个1*n的格子，将五行填上去，每格填一个，要求相邻格以及首尾格不能是同我和相克的关系，请问一共有多少种不同的方案？

输入

多组样例，每组一个整数n(0≤n≤10)，如果n为0，表示输入结束，这个样例不需要处理。

输出

每行输出一个样例的结果，因为数值可能非常大，请将结果对10+7取模。

样例输入

样例输出

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,LL 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,LL len)

 {

     Matrix ww;

     int i,j,k,tmp;

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

     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;

         }

     }

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

     {

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

         {

             if(j==) tmp=;

             else tmp=j-;

             ww.mat[i][j]=ww.mat[i-][tmp];

         }

     }

     return ww;

 }

 struct Matrix M_add(Matrix cur,Matrix now,LL 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,LL n,LL 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(LL 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 n;

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

     {

         if(n==)break;

         if(n==)

         {

             printf("5\n");

             continue;

         }

         solve(n-);

     }

     return ;

 }