HDU 1005 – Number Sequence [矩阵快速幂]

点击打开HDU题目链接

题意

给你一个递推公式f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.已知A,B,n,求f(n).

分析

一年前用C语言就AC了这道题,昨天拿过来准备水一发,发现要么TLE要么WA,貌似后台数据加强了,以前找周期的做法行不通了,网上很多题解可以验证是巧合AC的。还好后来学会了矩阵快速幂,又是一道水题了,矩阵很好推,不再赘述,直接看代码。

C++代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 4;
int N = 2;

struct Mat {
    int a[MAXN][MAXN];
    Mat() { memset(a, 0, sizeof(a)); }
    Mat multiMod(const Mat & y, const int mod) {
        Mat res;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * y.a[k][j]) % mod;
        return res;
    }
    Mat powerMod(int k, int mod) {
        Mat res, base = *this;
        for(int i = 0; i < MAXN; i++)
            res.a[i][i] = 1;
        while(k > 0) {
            if(k & 1)
                res = res.multiMod(base, mod);
            base = base.multiMod(base, mod);
            k >>= 1;
        }
        return res;
    }
};

int main() {
    int a, b, n;
    while(cin >> a >> b >> n, a||b||n) {
        if(n==1 || n==2) { puts("1"); continue; }
        Mat A, B;
        A.a[0][0] = A.a[1][0] = 1;
        B.a[0][0] = a;
        B.a[0][1] = b;
        B.a[1][0] = 1;
        B = B.powerMod(n-2, 7);
        B = B.multiMod(A, 7);
        cout << B.a[0][0] << endl;
    }
    return 0;
}

欢迎留言