矩阵乘法模板：

1 #define N 801 2 #include
     
       3 using namespace std; 4 #include
      
        5 int a[N][N],b[N][N],c[N][N]; 6 int n,m,p; 7 int read() 8 { 9     int ans=0,ff=1;char s;10     s=getchar();11     while(s<'0'||s>'9') 12     {13         if(s=='-') ff=-1;14         s=getchar();15     }16     while(s>='0'&&s<='9')17     {18         ans=ans*10+s-'0';19         s=getchar();20     }21     return ans*ff;22 } 23 int main()24 {25     n=read();26     p=read();27     m=read();28     for(int i=1;i<=n;++i)29       for(int j=1;j<=p;++j)30       a[i][j]=read();31     for(int i=1;i<=p;++i)32       for(int j=1;j<=m;++j)33       b[i][j]=read();34      for(int i=1;i<=n;++i)35       {36            for(int j=1;j<=m;++j)37        {38            c[i][j]=0;39            for(int k=1;k<=p;++k)40            c[i][j]+=a[i][k]*b[k][j];41            printf("%d ",c[i][j]);42        }43        printf("\n");44       }45     return 0;46  }
      
     

 

cojs 1717. 数学序列

★   输入文件：number1.in   输出文件：number1.out   简单对比

时间限制：1 s   内存限制：128 MB

【题目描述】

 

已知一个函数f :

f (1) =1

f (2) =1

f (n) = (a × f (n −1) +b × f (n − 2))mod 7

现给出a,b,n ,要你求出 f (n) .

 

【输入格式】

每一行输入一组数据分别为A,B,N(1<=A,B<=1000,1<=N<=200000000)

【输出格式】

每一行输出结果 f (n) .

【样例输入】

1 1 3

1 2 10

【样例输出】

25

1 #include
     
       2 using namespace std; 3 #include
      
        4 #include
       
         5 #define N 5 6 #define mod 7 7 struct Jz{ 8     int line,cal; 9     int jz[N][N];10 }a,ans;11 int A,B;12 void pre_chuli()13 {14     a.cal=2;a.line=2;15     a.jz[1][1]=0;a.jz[1][2]=1;16     a.jz[2][1]=B;a.jz[2][2]=A;17     ans.cal=1;ans.line=2;18     ans.jz[1][1]=1;19     ans.jz[2][1]=1;20 }21 Jz matrax(Jz x,Jz y)22 {23     Jz sum;24     sum.line=x.line;sum.cal=y.cal;25     memset(sum.jz,0,sizeof(sum.jz));26     /* for(int i=1;i<=sum.line;++i)27     {28      for(int j=1;j<=sum.cal;++j)29          printf("%d ",sum.jz[i][j]);30       printf("\n");31     }*/32     for(int i=1;i<=sum.line;++i)33       for(int j=1;j<=sum.cal;++j)34       {35           for(int k=1;k<=x.cal;++k)36           {37               sum.jz[i][j]=(sum.jz[i][j]+x.jz[i][k]*y.jz[k][j])%mod;38           }39       }40     return sum;41 }42 int Fast_matrax(int n)43 {44     if(n==1) return ans.jz[2][1];45     n-=2;/*真正的乘法次数是n-2*/46     while(n)47     {48         if(n&1)49         {50             ans=matrax(a,ans);51         }52         n>>=1;53         a=matrax(a,a);54     }55     return ans.jz[2][1]%mod;56 }57 int main()58 {59     freopen("number1.in","r",stdin);60     freopen("number1.out","w",stdout);61     int n;62     while(scanf("%d%d%d",&A,&B,&n)==3)63     {64         memset(a.jz,0,sizeof(a.jz));65         a.cal=a.line=0;66         memset(ans.jz,0,sizeof(ans.jz));67         ans.cal=ans.line=0;68         pre_chuli();69         printf("%d\n",Fast_matrax(n));70     }71     fclose(stdin);fclose(stdout);72     return 0;73 }