dutacm.club Water Problem（矩阵快速幂）

Water Problem

Time Limit:3000/1000 MS (Java/Others)   Memory Limit:163840/131072 KB (Java/Others)
Total Submissions:1228   Accepted:121

[Submit][Status][Discuss]

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 3
1 2 5

Sample Output

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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
using 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<N;i++)
            for(int j=0;j<N;j++)
                a[i][j]=(i==j);
    }
    Fast_Matrax operator * (const Fast_Matrax &B)const
    {
        Fast_Matrax C;
        for(int i=0;i<N;i++)
            for(int k=0;k<N;k++)
                for(int j=0;j<N;j++)
                    C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j]%mod+mod)%mod;
        return C;
    }
    Fast_Matrax operator ^ (const int &t)const
    {
        Fast_Matrax A=(*this),res;
        res.init();
        int p=t;
        while(p)
        {
            if(p&1)res=res*A;
            A=A*A;
            p>>=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;
}