【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution:

看到这道题,最先想说233333…

最先考虑到的方法,当然是直接暴力推,反正每个位置只与它左侧及上侧有关,推到要求的那个位置上就好,但是这样单组数据复杂度是\(O(nm)\),虽然有5000ms,但是一般这种题目数据量会很大,这样暴力绝对会超时,于是考虑到需要更快的迭代方法,第一列依次是\(0, a_1, a_2… a_n\),尝试在纸上把这个矩阵列出来,并且把每个位置上的值都只使用这些已知符号代替,我们发现一个规律,每个位置上的数实际上都把这一列它上方的所有数都加了进来,同理也把它左边的所有数都加了进来,进行简单的整理后,我们发现:每一行可以仅由上一行的值推出,每一列也可以仅由上一列的值推出。由上一行推的时候需要考虑到一个与输入相关的无规律常数,这个常数的存在破坏了递推形式不变性,所以只能够用刚才\(O(nm)\)复杂度的方法推;而由上一列推这一列时,我们需要考虑一个题目中拟定的嘲讽一般的233,它的规律很明显,由上一列到这一列,它的值扩10倍后加3便可完成这次递推,唯一不满足的就是最前面那一列的0。这时,注意到,在整个矩阵中,左上角的0是唯一一个不对结果产生贡献的值(并不是因为它是0,而是因为根据题设递推规则,它没有被加入到\(a_{nm}\)中),这样,它的值可以任意修改,那么我们便修改成23,这时每一列之间的递推形式固定的了下来,可以写出变换矩阵,之后使用矩阵快速幂来求解,复杂度降到\(O(n^3logm)\)。

总结一下,这道题关键是:

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果,是题设故意设计的一个坑。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 10000007;
const int LIM = 15;
struct Matrix {
    LL t[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}, size};
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

Matrix buildBase(int size) {
    Matrix ret = {{0}, size};
    ret.t[size - 1][size - 1] = 1;
    for (int i = size - 2; i >= 0; i--) {
        ret.t[i][0] = 10;
        ret.t[i][size - 1] = 1;
        for (int j = 1; j <= i; j++)
            ret.t[i][j] = 1;
    }
    return ret;
}

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{0}, m.size};
    for (int i = 0; i < ret.size; i++)
        ret.t[i][i] = 1;
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, m;
    LL ori[LIM];
    while (cin >> n >> m) {
        ori[0] = 23;
        ori[n + 1] = 3;
        for (int i = 1; i <= n; i++) cin >> ori[i];
        if (m == 0) cout << ori[n] << "\n";
        else {
            Matrix trans = powMod(m, buildBase(n + 2));
            LL ans = 0;
            for (int i = 0; i <= n + 1; i++)
                ans = (ans + trans.t[n][i] * ori[i]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}