题解 P3990 【[SHOI2013]超级跳马】

Shawk · 2020-08-15 21:35:16 · 题解

希丰展，看博客

这题题意很清楚了，DP也很容易想到，f_{i,j} 表示到达第i列第j行的方案数，将起点方案数设为 1，每个点的方案数由可以过来的点转移，一看数据范围，n 就 50，m 最大 1e9 ，这几乎就可以想到是矩阵快速幂优化了，我们可以一步一步分析。

首先不难得出一个 O(n^3) 的写法。（20pts）

f[1][1] = 1;
for (int i = 2; i <= m; ++i)
    for (int j = 1; j <= n; ++j)
        for (int k = i - 1; k >= 1; k -= 2)
            f[i][j] = (f[i][j] + f[k][j-1] + f[k][j] + f[k][j+1]) % M;

注意到这只是求前面的和，限制条件也只有只能从奇数行转移，这样让 f_{i,j} 记录上奇数行的和就能优化到 O(n^2。（50pts）
- 这里的f数组要同时记录前缀和，所以最终答案是类似区间求和的形式：f_{m,n} - f_{m-2,n}
- 为了方便最后矩阵的写法，又因为他是由倒数第二行最后两列转移过来，就直接输出 f_{m-1,n}+f_{m-1,n-1}
```
f[1][1] = 1;
for (int i = 2; i < m; ++i)
    for (int j = 1; j <= n; ++j)
        f[i][j] = (f[i-1][j] + f[i-1][j-1] + f[i-1][j+1] + f[i-2][j]) % M;
printf("%d\n", (f[m-1][n] + f[m-1][n-1]) % M);
```
发现第 i 列只由第 i-1 列和 i-2 列转移过来的，而且列数又那么大，考虑矩阵快速幂优化：
- 可以类比斐波那契数列的写法，将 f_{i.k}和f_{i-1,k}(k\in {1,...,n})的状态压成一个 1\times 2n 的矩阵，乘上一个转移矩阵，得到 f_{i+1.k}和f_{i,k}(k\in {1,...,n})的状态，转移矩阵根据上面第二个解法的转移方程构造，还是举 n=4 的例子

f_{i,1} & f_{i,2} &f_{i,3} &f_{i,4} &f_{i-1,1} &f_{i-1,2} &f_{i-1,3} &f_{i-1,4} \end{bmatrix} \ast \begin{bmatrix} 1 & 1 & 0& 0 & 1& 0 &0 & 0\\ 1& 1& 1 & 0& 0 &1 & 0 &0 \\ 0 & 1 & 1& 1& 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 &0 & 0 & 0 &1 \\ 1 & 0 &0 & 0 & 0 &0 & 0 &0 \\ 0& 1 & 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0 & 0&0&0 \\ 0& 0 & 0& 1 & 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} f_{i+1,1} & f_{i+1,2} &f_{i+1,3} &f_{i+1,4} &f_{i,1} &f_{i,2} &f_{i,3} &f_{i,4} \end{bmatrix}

~~这个式子有亿点长啊~~

转移矩阵：

1 & 1 & 0& 0 & 1& 0 &0 & 0\\ 1& 1& 1 & 0& 0 &1 & 0 &0 \\ 0 & 1 & 1& 1& 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 &0 & 0 & 0 &1 \\ 1 & 0 &0 & 0 & 0 &0 & 0 &0 \\ 0& 1 & 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0 & 0&0&0 \\ 0& 0 & 0& 1 & 0 & 0 & 0 & 0 \end{bmatrix}

初始矩阵

1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}

需要注意的几点：
1. 因为矩阵无法处理 m\le 2 的情况，所以需要特判。只有 f_{1,1},f_{1,2},f_{2,2}值为1,其他情况都是0.
2. 此解法只处理了 n>1 的情况，对于 n=1 的情况打表发现可以转换成斐波那契数列，而且此时转移矩阵与求斐波那契数列的转移矩阵也很想，也特判一下就好了。
接下来就是实现，具体看代码。

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105, M = 30011;

int n, n2, m;
struct Matrix {
    int a[N][N];
    Matrix () {
        memset(a, 0, sizeof(a));
    }
    int *operator [] (const int &i) {
        return a[i];
    }//重载方括号运算符，写起来方便
    Matrix operator * (const Matrix &b) {
        Matrix c;
        for (int i = 1; i <= n2; ++i)
            for (int j = 1; j <= n2; ++j)
                for (int k = 1; k <= n2; ++k)
                    (c.a[i][j] += a[i][k] * b.a[k][j] % M) %= M;
        return c;
    }//重载乘号
    void Print() {
        for (int i = 1; i <= n2; ++i, puts(""))
            for (int j = 1; j <= n2; ++j)
                printf("%d ", a[i][j]);
        puts("");
    }//调试输出用
}a, b, c;

Matrix Pow(Matrix a, int k) {
    Matrix ans = a; k--;
    for (; k; k >>= 1, a = a * a)
        if (k & 1) ans = ans * a;
    return ans;
}//快速幂

int main() {
    scanf("%d%d", &n, &m);
    if (m <= 2) {
        if (n <= 2 && m <= n) puts("1");
        else puts("0");
        return 0;
    }//特判情况1
    n2 = n << 1;
    for (int i = 1; i <= n; ++i) {//构造转移矩阵
        a[i][i-1] = a[i][i] = a[i][i+n] = a[i+n][i] = 1;
        if (i != n) a[i][i+1] = 1;
    }
    b = Pow(a, m - 2);
    if (n == 1) return printf("%d\n", b[1][1]), 0;//特判情况2
    int s1 = (b[1][n2-1] + b[2][n2-1] + b[n+1][n2-1]) % M;
    int s2 = (b[1][n2] + b[2][n2] + b[n+1][n2]) % M;
    //根据初始矩阵和快速幂后的转移矩阵求得目标矩阵的有用值
    printf("%d\n", (s1 + s2) % M);
    //s1是f[m-1][n-1]，s2是f[m-1][n]，加起来就是答案
    return 0;
}