萌新求助,矩阵快速幂
查看原帖
萌新求助,矩阵快速幂
107253
Water_Cows楼主2020/5/11 22:17

rtrt,为什么我错了/kk

五个TLE,五个WA

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 100 + 7;
const int MOD = 1e9 + 7;

int n, k;
struct mul
{
    ll d[N][N];
    mul()
    {
        memset(d, 0, sizeof(d));
    }
    inline void init()
    {
        for(int i=1; i<=n; i++) d[i][i] = 1;
    }
} a; 

mul operator * (const mul &x, const mul &y)
{
    mul z;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int t=1; t<=n; t++)
            {
                z.d[i][j] = (z.d[i][j] + x.d[i][t] * y.d[t][j] % MOD) % MOD;
            }
        }
    }
    return z;
}

inline mul ksm(mul a, int k)
{
    mul ans;
    ans.init();
    while(k)
    {
        if(k % 2 == 1) ans = ans * a;
        a = a * a;
        k >>= 1;
    }
    return ans;
}

inline void print(mul x)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            printf("%d ", x.d[i][j]);
        }
        puts("");
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d", &a.d[i][j]);
        }
    }
    mul ans = ksm(a, k);
    print(ans);
}

码风良心,请大佬查错。

拒绝无意义回复(如qndmx)

2020/5/11 22:17
加载中...