矩阵快速幂求调!
查看原帖
矩阵快速幂求调!
548203
KK_lang楼主2022/12/1 12:28

77 个点 RE、33 个点 WA,dalao 求调!

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int n;
long long k;

struct Matrix
{
    long long data[110][110];
    void clear()
    {
        memset(data, 0, sizeof(data));
    }
    void identity()
    {
        clear();
        for (int i = 1; i <= n; i++)
            data[i][i] = 1;
    }
}a, ans;

Matrix Mul(const Matrix &a, const Matrix &b)
{
    Matrix c;
    c.clear();
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                c.data[i][j] += (a.data[i][k] * b.data[k][j]) % mod;
                c.data[i][j] %= mod;
            }
    return c;
}

Matrix Pow(Matrix a, long long p)
{
    Matrix result;
    result.identity();
    Matrix base = a;
    while (p)
    {
        if (p & 1) result = Mul(result, base);
        base = Mul(base, base);
        p >>= 1;
    }
    return result;
}

void read()
{
    cin >> n >> k;
    a.clear();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a.data[i][j];
}

void write()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << ans.data[i][j] << " ";
       cout << endl;
    }
}

int main()
{
    cin >> n >> k;
    read();
    ans = Pow(a, k);
    write();
    return 0;
}
2022/12/1 12:28
加载中...