题目链接
题目大意
计算\(a^1+a^2+...+a^k\)
\(k\leq10^9,sz\leq30\)
\(a\)是矩阵
题目思路
要利用二分思想，感觉其实是分治的思想
我们先想一下\(a^1+a^2+a^3+a^4+a^5+a^6\)
这个式子怎么求
\(a^1+a^2+a^3+a^4+a^5+a^6=(1+a^3)(a^1+a^2+a^3)\)
那么你就可以如何写了
当\(k\)为奇数时
\(\sum_{i = 1}^k A^i = \sum_{i = 1}^{k -1} A^i + A^{k }\)
当\(k\)为偶数时
\(\sum_{i = 1}^k = \sum_{i = 1}^{k / 2} A^i + A^{k / 2}(\sum_{i = 1}^{k / 2}A^i)\)
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=31,inf=0x3f3f3f3f;
const double eps=1e-6;
int n,k,mod;
struct matrix{
int a[maxn][maxn];
}base,basetemp,ans,zero;
matrix mul(matrix a,matrix b){
matrix temp;
memset(temp.a,0,sizeof(temp.a)); //一定1要清空
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
temp.a[i][k]+=(a.a[i][j])*(b.a[j][k]);
temp.a[i][k]%=mod;
}
}
}
return temp;
}
matrix add(matrix a,matrix b){
matrix temp;
memset(temp.a,0,sizeof(temp.a)); //一定1要清空
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
temp.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
}
}
return temp;
}
matrix qpow(ll n,ll b){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans.a[i][j]=(i==j);
base.a[i][j]=basetemp.a[i][j];
}
}
while(b){
if(b&1){
ans=mul(ans,base);
}
base=mul(base,base);
b=b>>1;
}
return ans;
}
matrix dfs(int x){
if(x==0){
return zero;
}
if(x%2==1){
matrix temp1=qpow(n,x);
x--;
matrix temp2=dfs(x);
matrix tempsum=add(temp1,temp2);
return tempsum;
}else{
matrix temp1=qpow(n,x/2);
for(int i=1;i<=n;i++){
temp1.a[i][i]=(temp1.a[i][i]+1)%mod;
}
matrix temp2=dfs(x/2);
matrix tempsum=mul(temp1,temp2);
return tempsum;
}
}
signed main(){
scanf("%d%d%d",&n,&k,&mod);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&basetemp.a[i][j]);
}
}
matrix pr=dfs(k);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d%c",pr.a[i][j],j==n?‘\n‘:‘ ‘);
}
}
return 0;
}