acm-Matrix Power Series

发布时间:2014-10-23 23:24:52
来源:分享查询网

Matrix Power Series 时间限制:1000 ms |  内存限制:65535 KB 难度:4 描述 Givena n × n matrix A anda positive integer k, find thesum S = A + A2 + A3 +… + Ak. 输入 The input contains exactly one test case. The first line of inputcontains three positive integers n (n ≤ 30), k (k ≤ 10^9) and m (m< 10^4). Then follow n lines each containing n nonnegativeintegers below 32,768, giving A’s elements in row-major order. 输出 Output the elements of S modulo m in the same way as A isgiven. 样例输入 2 2 4 0 1 1 1 样例输出 1 2 2 3 来源 POJ Monthly 代码: #include   #include   #include   #define MAX 31  int n,m,k;  typedef struct snode{      intedge[MAX][MAX];  }Matrix;  Matrix map,ant,h,hh,c,d;    void mult(Matrix &a,Matrix &b,Matrix&c)  //矩阵C=A*B  {      inti,j,k2;     memset(h.edge,0,sizeof(h.edge));     for(i=0;i        for(j=0;j            for(k2=0;k2            {                 h.edge[i][j]+=(a.edge[i][k2]*b.edge[k2][j]); //**分开写,否则会WA                 h.edge[i][j]%=m;                             //**             }     for(i=0;i        for(j=0;j            c.edge[i][j]=h.edge[i][j];  }    Matrix KSM(Matrix a,intk)    //快速幂求矩阵A^k  {      inti;     memset(hh.edge,0,sizeof(hh.edge));     for(i=0;i        hh.edge[i][i]=1;     while(k>=1)     {         if(k&1)             mult(a,hh,hh);         mult(a,a,a);         k>>=1;     }      returnhh;  }    Matrix Sum(Matrix a,Matrix b)  //A,B矩阵相加  {      inti,j;     for(i=0;i        for(j=0;j        {             h.edge[i][j]=(a.edge[i][j]+b.edge[i][j]);             h.edge[i][j]%=m;         }      returnh;  }    Matrix F(int x)  {     if(x<=1)         return map;      elseif(x%2) //n为奇数:F[n]=F[n/2]+F[n/2]*A^(n/2)     {         c=F(x-1);         d=KSM(map,x);         return Sum(c,d);     }     else         //n为偶数:F[n]=F[n-1]+A^n     {         c=F(x/2);         d=KSM(map,x/2);  //二分减少规模         mult(c,d,d);         return Sum(c,d);     }  }    int main()  {      inti,j;     scanf("%d%d%d",&n,&k,&m);     for(i=0;i        for(j=0;j            scanf("%d",&map.edge[i][j]);     ant=F(k);     for(i=0;i    {         for(j=0;j        {             printf("%d",ant.edge[i][j]);             if(j!=n-1)               //每行最后的空格去掉,防PE                 printf(" ");         }         printf("\n");     }      return0;  } 

返回顶部
查看电脑版