HDOJ 1757 A Simple Math Problem

点击打开链接

题目意思：给定两个关系式，要求第k项模m的值，输入k 和 m

解题思路：

1 ：If x < 10 f(x) = x.
2 ：If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
3 ：f(0) , f(1) , ............ f(9)是常数存入一个cosnum数组中

4 ：（F(10)）= （A） * （F(9)） 这里的F区别于f , F(9)是一个常数矩阵
|f(10)| |a0 a1 a2 ...a8 a9| |f(9)|
| f(9) | | 1 0 0 ... 0 0 | |f(8)|
| ..... | = |.. ... ... ... .. | *| .. | = a0 * f(9) + a1 * f(8) + a2 * f(7) + …… + a9 * f(0);
| f(2) | | 0 0 0 ... 0 0 | |f(1)|
| f(1) | | 0 0 0 ... 1 0 | |f(0)|
由上面的等式可知F(11) = (A) * (F(10)) => (A) * ( (A) * F(9)) => (A)^2 * (F(9))
我们就可以知道求F(K) = (A)^(K-9) * (F(9));就转化为矩阵的快速幂问题，只要求出A的K-9次幂矩阵，然后用求出的ans矩阵的第一行乘上F（9），我们用倒着乘cosnum即可，注意求sum时候的取模运算

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const long long MAXN = 10;

long long k, mod, sum;
long long num[MAXN][MAXN];//所需的矩阵
long long cosnum[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};//常量数组

class Matrix { 
public:
    long long m[MAXN][MAXN];//public比较方便
    Matrix() {}
    
    //矩阵的数组初始化
    void init(long long num[MAXN][MAXN]) {
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < MAXN; j++) {
                m[i][j] = num[i][j];
            }
        }
    }
    
    //重载矩阵的乘法运算
    friend Matrix operator*(Matrix &m1, Matrix &m2) {
        int i, j, k;
        Matrix temp;
        for (i = 0; i < MAXN; i++) {
            for (j = 0; j < MAXN; j++) {
                temp.m[i][j] = 0;
                for (k = 0; k < MAXN; k++)
                    temp.m[i][j] += (m1.m[i][k] * m2.m[k][j]) % mod;
                temp.m[i][j] %= mod;
            }
        }
        return temp;
    }
    
    //矩阵的快速幂
    friend Matrix quickpow(Matrix &M, long long n) {
        Matrix tempans;//（对于矩阵的快速幂）是单位矩阵
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < MAXN; j++) {
                if (i == j)
                    tempans.m[i][j] = 1;
                else
                    tempans.m[i][j] = 0;
            }
        }
        //快速幂的运算
        while (n) {
            if (n & 1)
                tempans = tempans * M;
            n = n >> 1;
            M = M * M;
        }
        return tempans;
    }
};

int main() {
    Matrix A, ans;
    while (scanf("%lld%lld\n", &k, &mod) != EOF) {
        //初始化矩阵
        memset(num, 0, sizeof (num));
        for (int i = 0; i < 10; i++)
            scanf("%lld", &num[0][i]);
        for (int i = 1; i < MAXN; i++)
            num[i][i - 1] = 1;
        //判断
        if (k < 10)
            printf("%lld\n", k % mod);
        else {
            A.init(num); //初始化A矩阵
            ans = quickpow(A, k - 9); //求出矩阵的快速幂
            //求和
            sum = 0;
            for (int i = 0; i < MAXN; i++){
                sum += ((ans.m[0][i] * cosnum[MAXN-i-1]) % mod);//每一步都取模不影响结果
                sum %= mod;
            }
            printf("%lld\n", sum);
        }   
    }
}