迷之全部RE(矩阵快速幂模板)
查看原帖
迷之全部RE(矩阵快速幂模板)
461452
SunLegend楼主2023/7/15 20:04

自测样例和下载的测试点1都没问题,哪位大佬帮忙看一下?

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,k,a[202][202],ans[202][202];
long long aa[202][202];
long long pf()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            aa[i][j]=0;
            for(int k=1;k<=n;k++)
            {
                aa[i][j]=(aa[i][j]+a[i][k]*a[k][j]%mod)%mod;
            }
            //cout<<aa[i][j]<<' ';
        }
        //cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=aa[i][j];
        }
    }
}
long long cf()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            aa[i][j]=0;
            for(int k=1;k<=n;k++)
            {
                aa[i][j]=(aa[i][j]+ans[i][k]*a[k][j]%mod)%mod;

            }
            //cout<<aa[i][j]<<' ';
        }
        //cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ans[i][j]=aa[i][j];
        }
    }
}
long long ksm(long long y)
{

    while(y)
    {
        if(y&1)
        {
            cf();
        }
        pf();
        y>>=1;
    }
}
int main()
{
    scanf("%lld %lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lld",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++) ans[i][i]=1;
    ksm(k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%lld ",ans[i][j]);
        }
        putchar('\n');
    }
    return 0;
}


2023/7/15 20:04
加载中...