Water Problem

Time Limit:3000/1000 MS (Java/Others)   Memory Limit:163840/131072 KB (Java/Others)

Total Submissions:1228   Accepted:121

[][][]

Description

函数 $\mathrm{f:Z+\to Z}$

。已知 $\mathrm{f(1)，f(2)\; 的值，且对于任意\; x>1，有\; f(x+1)=f(x)+f(x-1)+sin(\pi x2)}$

。

求 $\mathrm{f(n)}$

的值。

Input

多组数据。（数据组数 $\mathrm{T\le 100}$

）

每组数据包含 $3$

$\mathrm{个不超过\; 109\; 的正整数，分别代表\; f(1)，f(2)\; 和\; n}$

的值。

Output

 输出 $\mathrm{f(n)mod(109+7)}$

。每组输出末尾有换行符。

Sample Input

1 2 31 2 5

Sample Output

37 【分析】矩阵快速幂裸题。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_backusing namespace std;typedef long long ll;const long long mod = 1e9+7;const long long N = 4;ll f1,f2;int n;struct Fast_Matrax{ ll a[N][N]; Fast_Matrax() { memset(a,0,sizeof(a)); } void init() { for(int i=0;i
              
               >=1; } return res; }}ans,tmp,x;int main(){ while(~scanf("%lld%lld%d",&f1,&f2,&n)) { x.a[0][0]=f2;x.a[0][1]=f1;x.a[0][2]=1,x.a[0][3]=0; if(n==1)printf("%lld\n",f1); else if(n==2)printf("%lld\n",f2); else { tmp.a[0][0]=1;tmp.a[0][1]=1;tmp.a[0][2]=0;tmp.a[0][3]=0; tmp.a[1][0]=1;tmp.a[1][1]=0;tmp.a[1][2]=0;tmp.a[1][3]=0; tmp.a[2][0]=0;tmp.a[2][1]=0;tmp.a[2][2]=0;tmp.a[2][3]=-1; tmp.a[3][0]=1;tmp.a[3][1]=0;tmp.a[3][2]=1;tmp.a[3][3]=0; ans=x*(tmp^(n-2)); printf("%lld\n",ans.a[0][0]); } } return 0;}