社区讨论
RE求助
P1939矩阵加速(数列)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo8gyaps
- 此快照首次捕获于
- 2023/10/27 18:27 2 年前
- 此快照最后确认于
- 2023/10/27 18:27 2 年前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1000000007;
struct Matrix{
vector< vector<int> > x;
inline int column() { return x.size(); }
inline int row() { return x[1].size(); }
};
inline int read(){
int w=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<1)+(w<<3)+(ch-48);
ch=getchar();
}
return w*f;
}
inline Matrix time(Matrix a,Matrix b){
//assert(a.column()==b.row());
int x=a.row(),y=b.column(),z=a.column();
Matrix ans;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
for(int k=1;k<=z;k++){
ans.x[i][j]+=a.x[i][k]*b.x[k][j]%MOD;
ans.x[i][j]%=MOD;
}
}
}
return ans;
}
inline Matrix qpow(Matrix a,int b){
assert(a.row()==a.column());
int x=a.row();
Matrix ans;
for(int i=1;i<=x;i++) ans.x[i][i]=1;
for(;b;b>>=1){
if(b&1) ans=time(ans,a);
a=time(a,a);
}
return ans;
}
signed main(){
int T;
T=read();
while(T--){
int n;
n=read();
Matrix a,b;
b.x[1][1]=1;b.x[1][2]=1;b.x[1][3]=1;
a.x[1][1]=1;a.x[1][2]=0;a.x[1][3]=1;
a.x[2][1]=1;a.x[2][2]=0;a.x[2][3]=0;
a.x[3][1]=0;a.x[3][2]=1;a.x[3][3]=0;
a=qpow(a,n-1);
b=time(b,a);
printf("%lld\n",b.x[1][1]);
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...