比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 矩阵幂之和 最终得分 100
用户昵称 胡嘉兴 运行时间 1.064 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2017-12-27 14:29:39
显示代码纯文本
#include<bits/stdc++.h>
#define N 37
#define ll long long
using namespace std;
ll n, m;
ll mul(ll a, ll b)
{
	return (ll)(a*b - (ll)(a/(long double)m*b+1e-6)*m + m)%m;
}
struct matrix
{
    ll A[N][N];
    void init()
    {
        memset(A, 0, sizeof(A));
        return;
    }
    matrix operator * (const matrix& a)const{
        matrix rel;
        rel.init();
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                for(int k = 1; k <= n; k++)
                {
                    rel.A[i][j] = (rel.A[i][j]+mul(A[i][k], a.A[k][j]))%m;
                }
            }
        }
        return rel;
    }
    matrix operator + (const matrix& a)const{
        matrix rel;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                rel.A[i][j] = (A[i][j]+a.A[i][j])%m;
            }
        }
        return rel;
    }
};
int main()
{
    ll k;
    matrix ans, t[2][3];
    freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout);
    scanf("%lld%lld%lld", &n, &k, &m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            scanf("%lld", &t[1][1].A[i][j]);
        }
    }
    k--;
    ans = t[1][2] = t[1][1];
    while(k)
    {
        if(k&1)
        {
            ans = (t[1][2]*ans)+t[1][1];
        }
        t[1][1] = t[1][1]+(t[1][2]*t[1][1]);
        t[1][2] = t[1][2]*t[1][2];
        k >>= 1;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            printf("%lld ", ans.A[i][j]);
        }
        puts("");
    }
    return 0;
}