矩阵快速幂求调
查看原帖
矩阵快速幂求调
580202
Siegerkranz_2735楼主2023/2/1 11:21

编译报错:

[Error] total size of local objects too large

代码:

#include<bits/stdc++.h>
#define N 1000000007
#define M 105
#define ll long long
using namespace std;
struct matrix{
	int n;
	ll a[N][N];
	matrix(){}
	matrix(int x){
		int n=x;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)a[i][i]=1;
	}
}A,C;
ll n,k;
matrix product(matrix A,matrix B){
	matrix ans;
	ans.n=A.n;
	for(int i=1;i<=ans.n;i++){
		for(int j=1;j<=ans.n;j++){
			ll sum=0;
			for(int k=1;k<=ans.n;k++){
				sum+=(A.a[i][k]*B.a[k][j])%M;
				sum%=M;
			}
			ans.a[i][j]=sum;
		}
	}
	return ans;
}
matrix matrix_pow(matrix A,int k){
	matrix ans,t=A;
	for(;k;t=product(t,t),k/=2)if(k&1)ans=product(ans,t);
	return ans;
}
int main(){
	cin>>n>>k;
	A.n=C.n=n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>A.a[i][j];
	C=matrix_pow(A,k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)cout<<C.a[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}
2023/2/1 11:21
加载中...