HDU 1757 A Simple Math Problem (矩阵快速幂)

题目

A Simple Math Problem

解析

矩阵快速幂模板题
构造矩阵
\[\begin{bmatrix}a_0&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\ 1&0&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0\\ 0&0&0&1&0&0&0&0&0&0\\ 0&0&0&0&1&0&0&0&0&0\\ 0&0&0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&1&0&0&0\\ 0&0&0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&0&0&1&0\\ \end{bmatrix}^{n-9} \begin{bmatrix}f_{n-1}\\f_{n-2}\\f_{n-3}\\f_{n-4}\\f_{n-5}\\f_{n-6}\\f_{n-7}\\f_{n-8}\\f_{n-9}\\f_{n-10} \end{bmatrix}=\begin{bmatrix}f{n}\\f_{n-1}\\f_{n-2}\\f_{n-3}\\f_{n-4}\\f_{n-5}\\f_{n-6}\\f_{n-7}\\f_{n-8}\\f_{n-9} \end{bmatrix}\]
然后套矩阵快速幂就完了。

代码

因为我的快速幂是直接用构造好的矩阵，不用再构造一个单位矩阵，所以幂的次数少1

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int n, m;
class matrix {
    public :
        int a[N][N];
        matrix() {
            memset(a, 0, sizeof(a));
        }
        matrix operator * (const matrix &oth) const {
            matrix ret;
            memset(ret.a, 0, sizeof(ret.a));
            for (int i = 1; i <= 10; ++i) 
                for (int j = 1; j <= 10; ++j)
                    for (int k = 1; k <= 10; ++k)
                        ret.a[i][j] = (ret.a[i][j] % m + (this->a[i][k] * oth.a[k][j]) % m) % m;
            return ret;
        }
} init;

template<class T>inline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}

matrix qpow(matrix a, int b) {
    matrix ans = init;
    while (b) {
        if (b & 1) ans = ans * a;
        b >>= 1, a = a * a;
    }
    return ans;
}

int f[N][N], ans;

signed main() {
    while (scanf("%lld%lld", &n, &m) != EOF) {
        ans = 0;
        memset(init.a, 0, sizeof(init.a));
        for (int i = 1; i <= 10; ++i) read(init.a[1][i]);
        if (n <= 9) {
            printf("%lld\n", n);
            continue;
        }
        for (int i = 2; i <= 10; ++i) init.a[i][i - 1] = 1;
        init = qpow(init, n - 10);
        for (int i = 1; i <= 10; ++i) ans += init.a[1][i] * (10 - i);
        printf("%lld\n", ans % m);
    }
}