BUPT2017 wintertraining(15) #6F
代码
代码语言：javascript复制#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#include <iostream>
using namespace std;
const ll mod=2147493647;
struct Mat{
int r,c;
ll a[10][10];
Mat(int _r,int _c){
r=_r;c=_c;
memset(a,0,sizeof a);
}
Mat operator *(const Mat &b)const{
Mat c(r,b.c);
for(int i=0;i<r;i )
for(int j=0;j<b.c;j )
for(int k=0;k<b.r;k ){
c.a[i][j]=(c.a[i][j] a[i][k]*b.a[k][j]%mod)%mod;
}
return c;
}
}A(7,7),B(7,1);
Mat qpow(Mat a,int b){
Mat c(a.r,a.c);
for(int i=0;i<a.r;i )c.a[i][i]=1;
while(b){
if(b&1)c=c*a;
b>>=1;
a=a*a;
}
return c;
}
int main() {
int at[10][10]={{1,2,1,4,6,4,1},
{1,0,0,0,0,0,0},
{0,0,1,4,6,4,1},
{0,0,0,1,3,3,1},
{0,0,0,0,1,2,1},
{0,0,0,0,0,1,1},
{0,0,0,0,0,0,1}};
for(int i=0;i<7;i )for(int j=0;j<7;j )A.a[i][j]=at[i][j];
int t,n,a,b;
cin>>t;
while(t--){
scanf("%d%d%d",&n,&a,&b);
B.a[0][0]=b;B.a[1][0]=a;
B.a[6][0]=1;
for(int i=5;i>1;i--)B.a[i][0]=B.a[i 1][0]*2;
if(n==1){
printf("%dn",a);
}else if(n==2){
printf("%dn",b);
}else{
Mat C=qpow(A,n-2)*B;
printf("%lldn",C.a[0][0]);
}
}
return 0;
}
