0
2
3
10

0
2
5
6497

C++解答

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
struct Matrix{
    LL m[4][4];
}E,D;
const LL mod=1000000007;
void init(){
    memset(E.m,0,sizeof(E.m));
    for(int i=1;i<=3;i++) E.m[i][i]=1;
}
Matrix multi(Matrix A,Matrix B){
    Matrix ans;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++){
        ans.m[i][j]=0;
        for(int k=1;k<=3;k++)
            ans.m[i][j]=(ans.m[i][j]+A.m[i][k]*B.m[k][j])%mod;
    }
    return ans;
}
Matrix Pow(Matrix A,LL k){
    Matrix ans=E;
    while(k){
        if(k&1) k--,ans=multi(ans,A);
        else k/=2,A=multi(A,A);
    }
    return ans;
}
Matrix Pow(Matrix A,string n){
    Matrix tmp=A,ans=E;
    for(int i=n.size()-1;i>=0;i--){
        ans=multi(ans,Pow(tmp,(LL)n[i]-'0'));
        tmp=Pow(tmp,10);
    }
    return ans;
}
int main(){
    /*freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);*/
    init(); memset(D.m,0,sizeof(D.m)); D.m[1][1]=2,D.m[1][2]=D.m[2][1]=D.m[3][2]=1,D.m[1][3]=3;
    string n;
    while(cin>>n){
        if(n=="0"){
            printf("0\n"); continue;
        }
        else if(n=="1"){
            printf("1\n"); continue;
        }
        else{
            int tp=2;
            for(int i=n.size()-1;tp!=0 && i>=0;i--){
                if(n[i]-'0'>=tp){
                    n[i]=n[i]-tp;
                    tp=0;
                }
                else{
                    n[i]=n[i]+10-tp;
                    tp=1;
                }
            }
        }
        Matrix tmp; tmp.m[1][1]=2,tmp.m[2][1]=1,tmp.m[3][1]=0;
        printf("%lld\n",multi(Pow(D,n),tmp).m[1][1]);
    }
    return 0;
}