nyoj 301繰返し値

プッシュ値
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
4
説明
プッシュ式をあげます.
f(x)=a*f(x-2)+b*f(x-1)+c
そして、f(1)、f(2)の値をあげて、f(n)の値を要求します.f(n)の値が大きすぎる可能性があるので、f(n)が100007に対して型を取った値を求めます.
注意:-1対3の型抜き後は2になります
入力
1行目は整数Tであり、テストデータのグループ数を表す(T<=10000)
その後、各行には6つの整数があり、それぞれf(1)、f(2)、a、b、c、nの値を表す.
このうち0<=f(1),f(2)<100,−100<=a,b,c<=100,1<=n<=1,00000000(10^9)
しゅつりょく
出力f(n)対100007型取り後の値
サンプル入力

2
1 1 1 1 0 5
1 1 -1 -10 -100 3

サンプル出力
5
999896
この問題はマトリクスの高速べき乗で行うことができ、マトリクス【f(x-2),f(x-1),c】*A=【f(x-1),f(x),c】を構築することができる.
      0 a 0
A= 1 b 0
       0 1 1

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 0x7fffffff
#define pi acos(-1.0)
#define MOD 1000007
ll ans[3][3];
ll a,b;
ll fast_mod(ll n)
{
    ll i,j,k;
    ll t[3][3]={0,a,0,1,b,0,0,1,1};
    ll temp[3][3];
    while(n)
    {
        if(n&1){
            for(i=0;i<3;i++){
                for(j=0;j<3;j++){
                    temp[i][j]=ans[i][j];
                    ans[i][j]=0;
                }
            }
            for(i=0;i<3;i++){
                for(j=0;j<3;j++){
                    for(k=0;k<3;k++){
                        ans[i][j]=(ans[i][j]+(temp[i][k]*t[k][j]%MOD) )%MOD;
                    }
                    ans[i][j]=(ans[i][j]+MOD)%MOD;
                }
            }
        }
        for(i=0;i<3;i++){
            for(j=0;j<3;j++){
                temp[i][j]=t[i][j];
                t[i][j]=0;
            }
        }
        for(i=0;i<3;i++){
            for(j=0;j<3;j++){
                for(k=0;k<3;k++){
                    t[i][j]=(t[i][j]+(temp[i][k]*temp[k][j]%MOD) )%MOD;
                }
                t[i][j]=(t[i][j]+MOD)%MOD;
            }
        }
        n>>=1;
    }
}
int main()
{
    ll n,m,i,j,T,k;
    ll c,d,e;
    ll f[3];
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld%lld",&f[1],&f[2],&a,&b,&c,&n);
        if(n==1 || n==2){
            printf("%lld
",(f[n]+MOD)%MOD );
            continue;
        }
        memset(ans,0,sizeof(ans));
        ans[0][0]=ans[1][1]=ans[2][2]=1;
        fast_mod(n-1);

        ll cnt; //            
        cnt=( (f[1]*ans[0][0]+f[2]*ans[1][0]+c*ans[2][0])%MOD+MOD)%MOD;
        printf("%lld
",cnt);

    }
    return 0;
}