Choosing number

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4973

推出递推公式， 数据范围那么大， 矩阵乘法。

const int MM = 100011;
const double eps = 1e-10;
#define maxint 10000000
#define mod 1000000007
#define debug puts("wrong");
//typedef __int64 int64;
typedef long long int64;
//const __int64 maxint = 1000000000000;
int64 N,M,K;

const int maxn = 3; //矩阵大小
struct Matrix {
    int r, c; //矩阵大小
    int64 a[maxn][maxn];
    //初始化
    Matrix(int r,int c):r(r), c(c) {memset(a,0,sizeof(a));}    
    //重写(),方便存取
    int64& operator() (int i,int j) {return a[i][j];}
    //O(N^3) 矩阵乘法
    Matrix operator*(const Matrix&B) {
        Matrix M(r,B.c);
        for(int i=0;i<r;i++) {
            for(int j=0;j<B.c;j++) {
                for(int k=0;k<c;k++) {
                    M.a[i][j]=(M.a[i][j]+a[i][k]*B.a[k][j])%mod;
                }
            }
        }
        return M;
    }
    Matrix operator^(int n) {
        Matrix M(r,c);
        for(int i=0;i<r;i++) M(i,i)=1;
        Matrix A=*this;
        for(;n;n>>=1,A=A*A) if(n&1) M=A*M;
        return M;
    }
    void out() {
        for(int i=0;i<r;i++) {
            for(int j=0;j<c;j++) {
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
    }
};

void solve() {
    int i,j,k;
    Matrix ans(2,2), tmp(1,2);
    ans(0,0)=ans(1,0)=M-K;
    ans(0,1)=K; ans(1,1)=K-1;
    tmp(0,0)=M-K; tmp(0,1)=K;
    ans=ans^(N-1);
    ans=tmp*ans;
    printf("%lld\n",(ans.a[0][0]+ans.a[0][1])%mod);
}

int main() {
    while(scanf("%lld%lld%lld",&N,&M,&K)!=EOF) solve();
    return 0;
}