程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> [HDU 1757] A Simple Math Problem （矩陣快速冪）

[HDU 1757] A Simple Math Problem （矩陣快速冪）

編輯：關於C

題目大意：

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
現在給你k和m，求f(k) % m。

解題思路：

f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)

其中k為10^9數量級，必然不能用遞推的方式做。這類題目可以通過構造矩陣，用矩陣快速冪來做。

構造的矩陣是:

|0 1 0 ......... 0| |f0| |f1 |
|0 0 1 0 ....... 0| |f1| |f2 |
|................1| * |..| = |...|
|a9 a8 .........a0| |f9| |f10|

代碼：

/*
ID: [email protected]
PROG:
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
const int maxn = 20;
const int maxm = 20;
ll mod, k;
struct Matrix {
    int n, m;
    int a[maxn][maxm];
    void clear() {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
    Matrix operator * (const Matrix &b) const { //實現矩陣乘法
        Matrix tmp;
        tmp.clear();
        tmp.n = n; tmp.m = b.m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < b.m; j++)
                for (int k = 0; k < m; k++) {
                    tmp.a[i][j] += a[i][k] * b.a[k][j];
                    tmp.a[i][j] %= mod;
                }
        return tmp;
    }
};
Matrix A, B;
void init() {
    A.clear(); //矩陣A是構造的矩陣
    A.n = A.m = 10;
    for (int i = 0; i < 9; i++)
        A.a[i][i + 1] = 1;
    B.clear();
    B.n = 10; B.m = 1; //矩陣B是f(x)的前10個數
    for (int i = 0; i < 10; i++)
        B.a[i][0] = i;
}
Matrix Matrix_pow(Matrix A, ll k, ll mod) { //矩陣快速冪
    Matrix res;
    res.clear();
    res.n = res.m = 10;
    for (int i = 0; i < 10; i++) res.a[i][i] = 1;
    while(k) {
        if (k & 1) res = A * res;
        k >>= 1;
        A = A * A;
    }
    return res;
}
int main () {
    init();
    while(cin>>k>>mod) {
        int x;
        for (int i = 0; i < 10; i++) {
            scanf("%d", &x);
            A.a[9][9 - i] = x;
        }
        if (k < 10) {
            printf("%lld\n", k % mod);
        }
        else {
            Matrix res = Matrix_pow(A, k - 9, mod);
            res = res * B;
            cout<