fuzhou 1683 纪念SlingShot ***

Problem 1683 纪念SlingShot

Accept: 361 Submit: 1287
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。

Input

第一行是一整数m，代表总共有m个cases。

Output

对于每个case，输出一行。格式见样例，冒号后有一个空格。

Sample Input

2 3 6

Sample Output

Case 1: 37 Case 2: 313

Source

FOJ月赛-2009年2月- Coral

Submit Back Status

题意不看，刚开始觉得好水。直接快速幂就可以做。

后来发现求和的，囧...

————————————————————————————

 /*

 矩阵构造：

 假设前N项和为S(n), 那么可以推出 S(n)=S(n-1)+f(n);

 得到一个矩阵:

 | 1 1 0 0 | | s(n-1) |   |  S(n)  |

 | 0 3 2 7 | |  f(n)  | = | f(n+1) |

 | 0 1 0 0 | | f(n-1) |   |  f(n)  |

 | 0 0 1 0 | | f(n-2) |   | f(n-1) |

 然后每一个N，一次快速幂，过了？额，下面就是这样的代码

 超时ing...

 那么就要优化了。优化：题目中矩阵是不变的，只是单纯的问

 n的值。保存2^i的结果。每一个数字都能由2^i组成。（二进制优化）

 这样就节省了很多的时间。

 484 ms

 特别注意：

 在最初的编写过程中，我只是用 (M_tom.mat[1][1]*4+M_tom.mat[1][2]*5)%mod;

 这样做的结果是答案偏小了。问题在于还要加上 (M_tom.mat[1][3]*3+M_tom.mat[1][4]*1);

 这就是数学的问题了.....囧

 动手试一试

 */

 /*

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 typedef __int64 LL;

 const __int64 mod=2009;

 struct Matrix

 {

     LL mat[6][6];

     void ini()

     {

         memset(mat,0,sizeof(mat));

     }

     void first_ini()

     {

         for(LL i=1;i<=4;i++)

         for(LL j=1;j<=4;j++)

         if(i==j) mat[i][j]=1;

         else mat[i][j]=0;

     }

 }M_hxl,M_tom;

 void make_first()

 {

     M_hxl.mat[1][1]=1;M_hxl.mat[1][2]=1;M_hxl.mat[1][3]=0;M_hxl.mat[1][4]=0;

     M_hxl.mat[2][1]=0;M_hxl.mat[2][2]=3;M_hxl.mat[2][3]=2;M_hxl.mat[2][4]=7;

     M_hxl.mat[3][1]=0;M_hxl.mat[3][2]=1;M_hxl.mat[3][3]=0;M_hxl.mat[3][4]=0;

     M_hxl.mat[4][1]=0;M_hxl.mat[4][2]=0;M_hxl.mat[4][3]=1;M_hxl.mat[4][4]=0;

 }

 Matrix Multiply(Matrix cur,Matrix now)

 {

     Matrix ww;

     ww.ini();

     for(LL i=1;i<=4;i++)

     for(LL k=1;k<=4;k++)

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

     {

         for(LL j=1;j<=4;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;

 }

 void power_sum2(LL n)

 {

       M_tom.first_ini();

       while(n)

       {

           if(n&1)

           {

               M_tom=Multiply(M_hxl,M_tom);

           }

           n=n>>1;

           M_hxl=Multiply(M_hxl,M_hxl);

       }

       LL sum=0;

       sum=(sum+M_tom.mat[1][1]*4)%mod;

       sum=(sum+M_tom.mat[1][2]*5)%mod;

       sum=(sum+M_tom.mat[1][3]*3)%mod;//!!!开始时没有加

       sum=(sum+M_tom.mat[1][4]*1)%mod;//!!!开始时没有加

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

 }

 int main()

 {

     LL T,n,i;

     while(scanf("%I64d",&T)>0)

     {

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

         {

             scanf("%I64d",&n);

             printf("Case %I64d: ",i);

             if(n==0)printf("1\n");

             else if(n==1) printf("4\n");

             else if(n==2) printf("9\n");

             else

             {

                 make_first();

                 power_sum2(n-1);

             }

         }

     }

     return 0;

 }

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 typedef __int64 LL;

 const __int64 mod=;

 struct Matrix

 {

     LL mat[][];

     void ini()

     {

         memset(mat,,sizeof(mat));

     }

     void first_ini()

     {

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

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

         if(i==j) mat[i][j]=;

         else mat[i][j]=;

     }

     void init()

     {

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

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

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

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

     }

 }M_hxl[],M_tom;

 Matrix Multiply(Matrix cur,Matrix now)

 {

     Matrix ww;

     ww.ini();

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

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

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

     {

         for(LL j=;j<=;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;

 }

 void power_sum2(LL n)

 {

       M_tom.first_ini();//！！

       LL cnt=;

       while(n)

       {

           if(n&)

           {

               M_tom=Multiply(M_hxl[cnt],M_tom);

           }

           n=n>>;

           cnt++;//模拟二进制.

       }

       LL sum=;

       sum=(sum+M_tom.mat[][]*)%mod;

       sum=(sum+M_tom.mat[][]*)%mod;

       sum=(sum+M_tom.mat[][]*)%mod;//!!!开始时没有加

       sum=(sum+M_tom.mat[][]*)%mod;//!!!开始时没有加

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

 }

 void pripare()

 {

     LL i;

     M_hxl[].init();

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

     M_hxl[i]=Multiply(M_hxl[i-],M_hxl[i-]);

 }

 int main()

 {

     LL T,n,i;

     pripare();//打表。

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

     {

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

         {

             scanf("%I64d",&n);

             printf("Case %I64d: ",i);

             if(n==)printf("1\n");

             else if(n==) printf("4\n");

             else if(n==) printf("9\n");

             else

             {

                 power_sum2(n-);

             }

         }

     }

     return ;

 }

纪念SlingSh