define mod 1000000007

<br />

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;
}

Java解答

import java.util.*;
import java.math.*;

public class Main {
	public static class Solve{
		class M{
			public long[][] m;
			public M(){
				m = new long[3][3];
				for(int i=0; i<3; i++){
					Arrays.fill(m[i], 0);
				}
			}
			
			public void print(){
				for(int i=0;i<3;i++){
					for(int j=0;j<3;j++){
						System.out.print(m[i][j] + " ");
					}
					System.out.println();
				}
			}
		}
		private M D,E;
		private final long mod = 1000000007;
		
		public Solve(){
			D = new M();
			E = new M();
			for(int i=0;i<3;i++){
				E.m[i][i] = 1;
			}
			D.m[0][2]=3;
			D.m[0][0]=2;
			D.m[0][1]=D.m[1][0]=D.m[2][1]=1;
		}
		
		private M mul(M x, M y){
			M ans = new M();
			for(int i=0; i<3; i++){
				for(int j=0; j<3; j++) if(x.m[i][j] != 0){
					for(int k=0; k<3; k++){
						ans.m[i][k] = (ans.m[i][k] + x.m[i][j] * y.m[j][k]%mod)%mod;
					}
				}
			}
			return ans;
		}
		
		private M Pow(BigInteger a){
			M d=E, t=D;
			BigInteger two = BigInteger.valueOf(2);
			while(a.equals(BigInteger.ZERO) == false){
				if(a.mod(two).equals(BigInteger.ONE)){
					d = mul(d,t);
				}
				a = a.divide(two);
				t = mul(t,t);
			}
			return d;
		}
		
		public long solve(BigInteger s){
			BigInteger two = BigInteger.valueOf(2);
			if(s.equals(BigInteger.ZERO)){
				return 0;
			}else if(s.equals(BigInteger.ONE)){
				return 1;
			}else if(s.equals(two)){
				return 2;
			}else{
				M p = Pow(s.subtract(two));
				return (p.m[0][0]*2 + p.m[0][1])% mod;
			}
		}
	}
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			BigInteger s = in.nextBigInteger();
			System.out.println(new Solve().solve(s));
		}
	}
}