Jzzhu and Sequences(CF #257 Div. 2)

一道规律题，比较简单。

题目大意：给出一个公式 f [ n ]=f [ n-1 ] - f [ n-2 ]，然后给出 f [ 1 ]和f [ 2 ]的值，以及n，求f [ n ]。附链接：http://codeforces.com/problemset/problem/450/B。

大体思路：因为所给的n很大，所以直接循环n次肯定超时。第一种方法，可以找一下规律，一般公式题都有规律可循，第二种，用矩阵快速幂暴力破解。第一种，通过对样例 1给出的两个数求 f [ n ]，可以发现循环节是6，然后此时由公式 f [ 3 ] = f [ 2 ] - f [ 1 ] 再来推，可以发现第6次的时候得到的 f [ 6 ] = f [ 2 ] - f [ 1 ]。

1. 找规律：

#include<iostream>
using namespace std;

int main(){
    int x,y;
    while(cin>>x>>y){
        int n;
        cin>>n;
        int f1=x;
        int f2=y;
        int f3;
        if(n==1){
            if(x<0)
                cout<<(1000000007+x)<<endl;
            else
                cout<<x%1000000007<<endl;
        }
        else if(n==2){
            if(y<0)
                cout<<(1000000007+y)<<endl;
            else
                cout<<y%1000000007<<endl;
        }
        else{
            n=(n-3)%6+3;
            for(int i=3;i<=n;i++){
                f3=f2-f1;
                if(f2<0)
                    f2=f2+1000000007;
                else
                    f2=f2%1000000007;
                f1=f2;
                if(f3<0)
                    f3=f3+1000000007;
                else
                    f3=f3%1000000007;
                f2=f3;
            }
            if(f3<0)
                cout<<(f3+1000000007)<<endl;
            else
                cout<<f3%1000000007<<endl;
        }
    }
    return 0;
}
           

2. 矩阵快速幂，这个方法有固定的步骤，把矩阵构造出来就好了。代码如下：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=2;
const long long mod=1000000007;
struct Matrix{
    long long mat[maxn][maxn];
};
Matrix unit;
Matrix mul(Matrix a,Matrix b){
    Matrix c;
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++){
            c.mat[i][j]=0;
            for(int k=0;k<maxn;k++){
                c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
                c.mat[i][j]%=mod;
            }
    }
    return c;
}
Matrix mat_pow(Matrix a,long long p){
    Matrix temp=unit;
    while(p){
        if(p%2)
            temp=mul(temp,a);
        a=mul(a,a);
        p/=2;
    }
    return temp;
}
int main(){
    memset(unit.mat,0,sizeof(unit.mat));
    for(int i=0;i<maxn;i++)
        unit.mat[i][i]=1;
    long long x,y,n;
    cin>>x>>y>>n;
    if(n==1){
        if(x<0)
            cout<<x+mod<<endl;
        else
            cout<<x%mod<<endl;
    }
    else if(n==2){
        if(y<0)
            cout<<y+mod<<endl;
        else
            cout<<y%mod<<endl;
    }
    else{
        Matrix A;      //初始矩阵，即包含f[1]、f[2]的矩阵
        A.mat[0][0]=x;
        A.mat[0][1]=y;
        A.mat[1][0]=A.mat[1][1]=0;
        Matrix C;     //系数矩阵
        C.mat[0][0]=0;
        C.mat[0][1]=-1;
        C.mat[1][0]=C.mat[1][1]=1;
        Matrix result=mat_pow(C,n-2);
        result=mul(A,result);
        if(result.mat[0][1]<0)
            cout<<result.mat[0][1]+mod<<endl;
        else
            cout<<result.mat[0][1]<<endl;
    }
}