【2016 ICPC瀋陽onsite C】Recursive sequence(マトリックス高速べき乗)
32578 ワード
問題面はあなたに1つの繰返し式F[n]=2∗F[n−2]+F(n−1)+n 4 F[n]=2*F[n−2]+F(n−1)+n^4 F[n]=2∗F[n−2]+F(n−1)+n 4 F(n)F(n)F(n)F(n)を求める.行列の高速べき乗は線形の繰返しを求めるのにしか使えないと思っていたが、あまりにも料理的だった.この問題母に対して、n 4 n^4 n 4があることに気づきました.私たちはどうしますか.n 4 n^4 n 4から(n+1)4(n+1)^4(n+1)4まで線形にはできないが,分解できるからである.(n+1)4=n 4+4′n 3+6′n 2+4′n 2+4′n+1(n+1)4′n+1(n+1)^4=n^4+4*n^3+6*n^2+6*n^2+4′*n+n+1(n+1)4=n 4+4′n n 3+6′n 2+4′n+4′n n+1をこのように類推して,行列の中でF(n),F(n+1),n 4,n 3,n 2,n,n,1 F(n),1 F(n n n n n n n n n n n n n n n,n n,1 F(n),F(n n n n n n n n n n n n n n n n n n n n^4,n^3,n^2,n,1 F(n),F(n+1),n 4,n 3,n 2,n,1を加えるとよい.係数に基づいてマトリクス要素を割り当てます.マトリクスの高速べき乗をもう一度セットすればいいです.
#include
using namespace std;
typedef long long ll;
const ll maxn = 1000;
const ll mod=2147493647;
struct mart{
ll m[100][100];
}unit;
mart mult(mart a,mart b){
mart ans;
for(ll i=0;i<9;i++){
for(ll j=0;j<9;j++){
ll x=0;
for(ll k=0;k<9;k++){
x+=(a.m[i][k]*b.m[k][j]);
x%=mod;
// cout<
}
ans.m[i][j]=x%mod;;
}
}
return ans;
}
void init(){
memset(unit.m,0,sizeof(unit.m));
for(ll i=0;i<9;i++){
unit.m[i][i]=1;
}
}
mart qpow(mart a,ll x){
init();
mart rt=unit;
while(x){
if(x&1) rt=mult(rt,a);
a=mult(a,a);
x>>=1;
}
return rt;
}
ll solve3(ll n,ll a1,ll b1){
mart a;
a.m[0][0]=0,a.m[0][1]=1,a.m[0][2]=0,a.m[0][3]=0,a.m[0][4]=0,a.m[0][5]=0,a.m[0][6]=0;
a.m[1][0]=2,a.m[1][1]=1,a.m[1][2]=1,a.m[1][3]=0,a.m[1][4]=0,a.m[1][5]=0,a.m[1][6]=0;
a.m[2][0]=0,a.m[2][1]=0,a.m[2][2]=1,a.m[2][3]=4,a.m[2][4]=6,a.m[2][5]=4,a.m[2][6]=1;
a.m[3][0]=0,a.m[3][1]=0,a.m[3][2]=0,a.m[3][3]=1,a.m[3][4]=3,a.m[3][5]=3,a.m[3][6]=1;
a.m[4][0]=0,a.m[4][1]=0,a.m[4][2]=0,a.m[4][3]=0,a.m[4][4]=1,a.m[4][5]=2,a.m[4][6]=1;
a.m[5][0]=0,a.m[5][1]=0,a.m[5][2]=0,a.m[5][3]=0,a.m[5][4]=0,a.m[5][5]=1,a.m[5][6]=1;
a.m[6][0]=0,a.m[6][1]=0,a.m[6][2]=0,a.m[6][3]=0,a.m[6][4]=0,a.m[6][5]=0,a.m[6][6]=1;
mart b;
// mart c=qpow(a,n-1);
b.m[0][0]=a1%mod;
b.m[1][0]=b1%mod;
b.m[2][0]=81;
b.m[3][0]=27;
b.m[4][0]=9;
b.m[5][0]=3;
b.m[6][0]=1;
mart ans=mult(qpow(a,n-1),b);
return ans.m[0][0]%mod;
}
int main(){
ll t;
cin>>t;
ll n,b,c;
while(t--){
cin>>n>>b>>c;
cout<<solve3(n,b,c)<<endl;
}
return 0;
}