HDU1757 A Simple Math Problem（矩阵快速幂）

February 25, 2016

题目链接

x < 10 时 f(x) = x. x >= 10 时 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10) 并且 ai(0<=i<=9) 只能是 0 或 1. 求 f(n)%m。 一张图一目了然。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const double pi = acos(-1);

int MOD;
const int maxn = 10;

struct Matrix{
    int mat[maxn][maxn];
};

//矩阵乘法
Matrix matrixmul(Matrix a,Matrix b){
    Matrix ret;
    for(int i = 0; i < maxn; i++)
        for(int j = 0; j < maxn; j++){
            ret.mat[i][j] = 0;
            for(int k = 0; k < maxn; k++){
                ret.mat[i][j] += (a.mat[i][k]*b.mat[k][j])%MOD;
                ret.mat[i][j] %= MOD;
            }
        }
    return ret;
}

// a^n%MOD
Matrix M_quickpow(Matrix a, long long n){
    Matrix ret;
    memset(ret.mat, 0, sizeof(ret.mat));
    //构造单位矩阵
    for(int i = 0; i < maxn; i++)
        ret.mat[i][i] = 1;
    while (n){
        if (n & 1) ret = matrixmul(ret, a);
        n >>= 1;
        a = matrixmul(a, a);
    }
    return ret;
}



int main(){
    //freopen("a.txt", "r", stdin);
    int k, m;
    Matrix q;
    memset(q.mat, 0, sizeof(q.mat));
    while (~scanf("%d%d", &k, &MOD)){
        if(k<10) cout << k%MOD << endl;
        else{
            for(int i = 0; i < 10; i++)
                scanf("%d", &q.mat[0][i]);
            for(int i = 0; i < 9; i++){
                q.mat[i+1][i] = 1;
            }

            Matrix aa = M_quickpow(q, k-9);
            Matrix x;
            memset(x.mat, 0, sizeof(x.mat));
            for(int i = 0; i < 10; i++)
                x.mat[i][0] = 9-i;

            Matrix ans = matrixmul(aa, x);

            cout << ans.mat[0][0] << endl;
        }

    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]