help! P1962
  • 板块灌水区
  • 楼主wangding
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/4/13 21:39
  • 上次更新2024/4/14 00:25:01
查看原帖
help! P1962
1113248
wangding楼主2024/4/13 21:39

样例过了,交上去Compile Error……

#include<bits\stdc++.h>
using namespace std;
struct matrix{
	int B[19][19];
};
int MAX=1000000007;
matrix mul(matrix q,matrix b){
	matrix ans;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			ans.B[i][j]=0;
		}
	}
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int l=1;l<=2;l++){
				ans.B[i][j]=(ans.B[i][j]+1ll*q.B[i][l]*b.B[l][j])%MAX;
			}
		}
	}
	return ans;
}
matrix ksm(matrix b,int s){
	matrix ans;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			ans.B[i][j]=0;
		}
	}
	for(int i=1;i<=2;i++){
		ans.B[i][i]=1;
	}
	while(s){
		if(s%2==1){
			ans=mul(ans,b);	
		}
		b=mul(b,b);
		s/=2;	
	}
	return ans;
}
int main(){
	int n;
	matrix b,p;
	cin>>n;
	memset(b.B,0,sizeof(b.B));
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			b.B[i][j]=1;
		}
	}
	b.B[2][2]=0;
	int ans=0;
	p=ksm(b,n-1);
	for(int i=1;i<=2;i++){
		ans+=p.B[1][i]*(2-i);
	}
	cout<<ans%MAX;
	return 0;
} 
2024/4/13 21:39
加载中...