POJ 3233-Matrix Power Series( S = A + A^2 + A^3 + … + A^k 矩阵快速幂取模)

比眉伴天荒 2022-09-24 15:27 120阅读 0赞

Matrix Power Series

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;20309</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;8524</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a *n* × *n* matrix *A* and a positive integer *k*, find the sum *S* = *A* \+ *A*2 \+ *A*3 \+ … + *Ak*.

Input

The input contains exactly one test case. The first line of input contains three positive integers *n* (*n* ≤ 30), *k* (*k* ≤ 109) and *m* (*m* < 104). Then follow *n* lines each containing *n* nonnegative integers below 32,768, giving *A*’s elements in row-major order.

Output

Output the elements of *S* modulo *m* in the same way as *A* is given.

Sample Input

2 2 4
    0 1
    1 1

Sample Output

1 2
    2 3

Source

[POJ Monthly--2007.06.03][], Huang, Jinsong

## 题目意思： ##

*已知n，k，m，S*  =  *A*  \+  *A* 2  \+  *A* 3  \+ … +  *Ak* . *求：S%m*

## 解题思路： ##

模板题，快速幂取模+二分优化。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #define INF 0xfffffff
    using namespace std;
    const long long MAXN=81;
    long long n,mod;
    struct Mat
    {
        long long m[MAXN][MAXN];
    };
    Mat a,per;
    void init()
    {
        long long i,j;
        for(i=0; i<n; ++i)
            for(j=0; j<n; ++j)
            {
                cin>>a.m[i][j];
                a.m[i][j]%=mod;
                per.m[i][j]=(i==j);
            }
    }
    
    Mat mul(Mat A,Mat B)
    {
        Mat ans;long long i,j,k;
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
            {
                ans.m[i][j]=0;
                for(k=0; k<n; k++)
                    ans.m[i][j]+=(A.m[i][k]*B.m[k][j]);
                ans.m[i][j]%=mod;
            }
        return ans;
    }
    Mat power(long long k)
    {
        Mat p,ans=per;
        p=a;
        while(k)
        {
            if(k&1)
            {
                ans=mul(ans,p);
                --k;
            }
            else
            {
                k/=2;
                p=mul(p,p);
            }
        }
        return ans;
    }
    
    Mat add(Mat a,Mat b)
    {
        Mat c;long long i,j;
        for(i=0; i<n; ++i)
            for(j=0; j<n; ++j)
                c.m[i][j]=(a.m[i][j]+b.m[i][j])%mod;
        return c;
    }
    Mat sum(long long k)
    {
        if(k==1) return a;
        Mat temp,b;
        temp=sum(k/2);
        if(k&1)
        {
            b=power(k/2+1);
            temp=add(temp,mul(temp,b));
            temp=add(temp,b);
        }
        else
        {
            b=power(k/2);
            temp=add(temp,mul(temp,b));
        }
        return temp;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        long long i,j,k;
        while(cin>>n>>k>>mod)
        {
            init();
            Mat ans=sum(k);
            for(i=0; i<n; ++i)
            {
                for(j=0; j<n-1; ++j)
                    cout<<ans.m[i][j]<<" ";
                cout<<ans.m[i][j]<<endl;
            }
        }
        return 0;
    }
    /**
    2 2 4
    0 1
    1 1
    **/

[POJ Monthly--2007.06.03]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.06.03