给定一个坐标系，可以往左，右，上走，已经走过的点（单次访问中）不可以重复走，一共可以走NN步，求一共有多少种走法。

题目分析

表神，各单位提供丰富成功地证明了递推公式，然而，不适合这样做的蒟蒻Sulfur6更喜欢打表找规律。

这里我们就假装我们已经打完了这个表，然后发现它的前几项分别是：

f(0)=1,f(1)=3,f(2)=7,f(3)=17,f(4)=41,f(5)=99 f(0) = 1, f(1) = 3, f(2) = 7, f(3) = 17, f(4) = 41, f(5) = 99

后面不打了T ^ T，所以我们发现了一个递推公式：

f(i)=f(i−2)+2×f(i−1) f(i) = f(i - 2) + 2 \times f(i - 1)

时间复杂度降至O(n)O(n)，但是极限数据高达10910^9，这时O(n)O(n)不靠谱。而且会MLE

矩阵

说矩阵优化之前先说说矩阵

形如

简而言之，矩阵是一坨数

矩阵乘法

对于两个大小为N×MN \times M和P×NP \times N的矩阵A,BA,B，他们相乘后的结果矩阵CC是一个大小为M×PM \times P的矩阵。 对于矩阵CC的每一位Ci,jC_{i,j}，有:

Ci,j=∑k=1NAi,k×Bk,j C_{i,j} = \sum\limits_{k = 1}^{N} A_{i,k} \times B_{k,j}

矩阵优化递推

团长并不知道这种玄学方法的由来，只知道我们可以用这种技巧来转移

这样相乘以后的结果:

也就是说我们可以通过矩阵相乘的方式来求出某递推公式的某一项，即:

如何优化

  • 矩阵满足结合律 既然如此，我们就可以出动大杀器，快速幂，这样就可以在O(logn)O(logn)的时间内求得递推公式的某一项了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
const int maxn = 1e9;
const int mo = 1e9 + 7;
struct Mat {
    long long a[2][2];
    Mat (const bool unit = false) { //构造函数，初始化矩阵值
        memset(a, 0, sizeof(a));
        if (unit) for (int i = 0; i < 2; i++) a[i][i] = i;//此处矩阵用于快速幂中作为单位矩阵承载答案
    }
    long long &operator()(const int i, const int j = 0)
        { return a[i][j]; }
    const long long &operator()(const int i, const int j = 0)
        const { return a[i][j]; } //重载运算符并引用，快速取得并修改某矩阵的值
};
Mat operator*(const Mat &a, const Mat &b) { //重载运算符，矩阵乘法
    Mat res(false);
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                (res(i, j) += a(i, k) * b(k, j)) %= mo;
    return res;
}
Mat pow(Mat a, int n) { //矩阵快速幂
    Mat res(true);
    for (; n; n >>= 1, a = a * a) if (n & 1) res = res * a;
    return res;
}
int main () {
    freopen("coordinate.in", "r", stdin);
    freopen("coordinate.out", "w", stdout);
    int n; scanf("%d", &n);
    
    if (n == 0) printf("1");
    else if (n == 1) printf("3");
    else {
        Mat init(false); //初始矩阵
        init(0) = 1;
        init(1) = 3;
        Mat mat(false); //转移矩阵
        mat(0, 0) = 0;
        mat(0, 1) = 1;
        mat(1, 0) = 1;
        mat(1, 1) = 2;
        Mat res = pow(mat, n - 1) * init; //此处转移矩阵的位置和初始矩阵的位置不可颠倒，因为矩阵不满足交换律
        printf("%lld\n", res(1));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

最后说几句

  • 这题中使用的矩阵特性就是满足结合律但是不满足交换律
  • 因为是考试的题所以说我还是打了文件输入输出
  • LaTeX公式和Markdown不兼容真是见鬼了
  • 公式打起来好麻烦
  • 这道题是可以分块打表的
  • 再次%表神cyr