矩阵快速幂模板0分求助
查看原帖
矩阵快速幂模板0分求助
381926
_Anonymous_楼主2023/3/21 21:35

蒟蒻人没了,这玩意还能0分,请大佬爆踩

#include<bits/stdc++.h>
#define debug cout << "OK" << endl;
#define MAXN int(1e6 + 10)
#define MAXM int(1e6 + 10)
#define Mod int(1e9+7)
using namespace std;

struct node
{
    long long mat[110][110];
    int a, b;
    node()
    {
    	a = b = 0; 
        memset(mat, 0, sizeof(mat));
        for(int i = 0; i < 100; i++)
        {
            mat[i][i] = 1;
        }
    }
    void print()
    {
    	for(int i = 0; i < a; i++)
		{
			for(int j = 0; j < b; j++)
			{
				printf("%lld ", mat[i][j]);
			}
			cout << endl;
		}
	}
};
node operator * (const node &x, const node &y)//x.b=y.a
{
    node ans;
    ans.a = x.a, ans.b = y.b;
    for(int i = 0; i < x.a; i++)
    {
        for(int j = 0; j < y.b; j++)
        {
            ans.mat[i][j] = 0;
            for(int k = 0; k < x.b; k++)
            {
                ans.mat[i][j] = (ans.mat[i][j] + x.mat[i][k] * y.mat[k][j] % Mod) % Mod;
            }
        }
    }
    return ans;
}
node mat_pow(const node &u, int y)
{

    node tmp, ans;
    tmp = u;
    ans.a = u.a, ans.b = u.b;
    while(y)
    {
        if(y & 1)
        {
            ans = ans * tmp;
        }
        y >>= 1;
        tmp = tmp * tmp;
    }
    return ans;
}

int main()
{
	int n, k;
	cin >> n >> k;
	node u;
	u.a = u.b = n;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			scanf("%lld", &u.mat[i][j]);
		}
	}
	mat_pow(u, k).print();
 	return 0;
}

2023/3/21 21:35
加载中...