Yet Another Number Sequence 题解

· · 题解

见数据范围知算法，很明显，矩阵快速幂！

但是矩阵快速幂只能解决 线性递推 的问题，所以我们需要转化！

怎么转呢？自已观察题目，可以发现最棘手的问题在这里：

A_i(k)=\color{orangered}i^k\color{black}F_i

这里因为 \color{orangered}i^k 的存在导致我们无法简单地转移，怎么办呢？

既然是 线性递推 ，我们就肯定要拆解，考虑使用 二项式定理 展开！

接下来使用二项式定理展开 (i+1)^k，来思考一下矩阵中需要保留的元素：

\begin{aligned}(i+1)^k=\sum^k_{n=0}\color{orangered}C_k^n\color{#AA00AA}i^n\end{aligned}

可以发现，转移需要所有的 \color{#AA00AA}i^n\color{black}(n\le k) ，而系数 \color{orangered}C_k^n\color{black}(n\le k) 都可以提前计算，并保存到矩阵中！

那不就简单了，带上 F_{i+1} 再来试一下：

(i+1)^kF_{i+1}&=(i+1)^kF_{i-1}+(i+1)^kF_i\\ &=[(i-1)+2]^kF_{i-1}+(i+1)^kF_i\\ &=\sum_{n=0}^k\color{orangered}2^{k-n}C_k^n\color{#AA00AA}(i-1)^nF_{i-1}\color{black}+\sum_{n=0}^k\color{orangered}C_k^n\color{#AA00AA}i^nF_i \end{aligned}

可以看到，我们只需要同时保留 \color{#AA00AA}(i-1)^nF_{i-1}\color{black}(n\le k) 和 \color{#AA00AA}i^nF_i\color{black}(n\le k)，它们的形式都是一样的，至于两种系数 \color{orangered}2^{k-n}C_k^n\color{black}(n\le k) 和 \color{orangered}C_k^n\color{black}(n\le k) 也可以提前计算存矩阵中！

那么我们就可以开始了！矩阵就定义成这样吧：

那么递推方程就应该长这样，照着上面的式子写，分分块，挺有规律的：

之中还有很多有趣的东西：

还有很多，你愿意的话可以自己发掘一下~

最后附上代码，带空格属于是老年人码风力：

#include <iostream>
#include <cstring>
using namespace std;

#define int unsigned long long
#define mod 1000000007

#define MATRIXSIZE 125
struct matrix {
    int m[MATRIXSIZE][MATRIXSIZE], w, h;
    matrix(int width, int height) : w(width), h(height) {
        memset(m, 0, sizeof(m));
    }
    int * operator [] (int p) {
        return m[p];
    }
    matrix operator * (matrix x) const {
        matrix res(x.w, h);
        for (int a = 1; a <= h; a ++)
            for (int b = 1; b <= x.w; b ++)
                for (int c = 1; c <= w; c ++)
                    res[a][b] = (res[a][b] +
                        m[a][c] * x[c][b] % mod) % mod;
        return res;
    }
    matrix operator ^ (int k) const {
        matrix res(w, w), times(*this);
        for (int i = 1; i <= w; i ++)
            res[i][i] = 1;
        while (k) {
            if (k & 1)
                res = res * times;
            times = times * times;
            k >>= 1;
        }
        return res;
    }
    void output() const {
        cout << "width: " << w << endl;
        cout << "height: " << h << endl;
        for (int i = 1; i <= 2; i ++) {
            cout << "[ ";
            for (int j = 1; j <= w; j ++)
                cout << m[i][j] << ' ';
            cout << ']' << endl;
        }
    }
};

int n, k;

int solvo() {
    int siz = 1 + ((++ k) << 1);
    matrix res(siz, 1), times(siz, siz);

    res[1][1] = res[1][2] = 1;
    for (int i = 2 + k; i <= siz; i ++)
        res[1][i] = 1;

    // 第一区
    times[1][1] = 1;

    // 第八区
    for (int i = 2; i <= 1 + k; i ++)
        times[i + k][i] = 1;

    // 第九区
    times[2 + k][2 + k] = 1;
    for (int i = 3 + k; i <= siz; i ++)
        for (int j = 2 + k; j <= i; j ++)
            times[j][i] = (times[j][i - 1] + times[j - 1][i - 1]) % mod;

    // 第六区
    for (int i = 2; i <= 1 + k; i ++)
        for (int j = i + k; j <= siz; j ++)
            times[i][j] = (times[i + k][j] << (j - i - k)) % mod;

    // 第四及第七区
    for (int i = 2; i <= siz; i ++)
        times[i][1] = times[i][siz];

    times = times ^ (n - 1);
    res = res * times;
    return res[1][1];
}

main() {
    cin >> n >> k;
    cout << solvo();
    return 0;
}

拜拜~