提交记录R84856667

矩阵快速幂

如下代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int MAX=2e5+5;
const ll P=1e9+7;
int n,l;
int a[MAX];
typedef vector<vector<ll>> mat;
void Mul(mat a,mat b,mat &ans)
{
	for(auto &v1:ans)
	{
		for(auto &v:v1)
		{
			v=0;
		}
	}
	for(int i=0;i<a.size();i++)
	{
		for(int k=0;k<b.size();k++)
		{
			for(int j=0;j<b[j].size();j++){
				ans[i][j]+=(a[i][k]*b[k][j])%P;
			}
		}
	}
	return;
}
void quick_pow(mat a,mat &ans,int b)
{
	for(int i=0;i<ans.size();i++)
	{
		ans[i][i]=1;
	}
	while(b)
	{
		if(b&1)
		{
			Mul(a,ans,ans);
		}
		Mul(a,a,a);
		b=b>>1;
	}
	return;
}
int main()
{
	cin>>n>>l;
	mat a,ans=mat(n,vector<ll>(n));
	a.resize(n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			ll tmp;
			cin>>tmp;
			a[i].push_back(tmp);
		}
	}
	quick_pow(a,ans,l);
	for(int i=0;i<ans.size();i++)
	{
		for(int j=0;j<ans[i].size();j++)
		{
			cout<<ans[i][j]<<' ';
		}
		cout<<endl;
	}
	return 0;
}