bzoj 4417 [Shoi2013]超级跳马

Description

现有一个n行m列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。例如，当n = 3, m = 10时，下图是一种可行的跳法。

试求跳法种数mod 30011。

Input

仅有一行，包含两个正整数n, m，表示棋盘的规模。

Output

仅有一行，包含一个整数，即跳法种数mod 30011。

Sample Input

3 5

Sample Output

10

HINT

对于100%的数据，1 ≤ n ≤ 50，2 ≤ m ≤ 10^9

题解

做一个3*n的矩阵，前n列表示距离下一行为奇数的每一列的答案的和，中间n列代表偶数的，最后n列代表最后一列的答案

#include <cstdio>
#include <cstring>
using namespace std;
int mn;
long long p;
const int mod = 30011;
#define MN 160
struct matrixs {
    int m[MN][MN];
    void clear() { memset(m, 0, sizeof m); }
    matrixs operator * (const matrixs &a) const {
        matrixs ans = {};
        for (int i = 1; i <= mn; i++)
            for (int k = 1; k <= mn; k++)
                if (m[i][k])
                    for (int j = 1; j <= mn; j++)
                        ans.m[i][j] = (ans.m[i][j] + (long long)m[i][k] * a.m[k][j]) % mod;
        return ans;
    }
    matrixs matrix_pow(long long p) {
        matrixs ans,a = (*this);
        ans.clear();
        for (int i = 1; i <= mn; i++) ans.m[i][i] = 1;
        for (; p; a = a * a, p >>= 1)
            if (p & 1) ans = ans * a;
        return ans;
    }
    void print() {
        for (int i = 1; i <= mn; ++i, puts(""))
            for (int j = 1; j <= mn; ++j)
                printf("%d ", m[i][j]);
        puts("");
    }
}a, b, c;
main() {
    int n;
    scanf("%d %lld", &n, &p);
    mn = n * 3;
    a.m[1][1] = a.m[1][n * 2 + 1] = 1;
    for (int i = 1; i <= n; ++i) {
        c.m[n + i][i] = c.m[i][n + i] = c.m[i][i] = 1;
        if (i != 1)
            c.m[i - 1][i] = c.m[i - 1][n * 2 + i] = 1;
        if (i != n)
            c.m[i + 1][i] = c.m[i + 1][n * 2 + i] = 1;
        c.m[i][n * 2 + i] = 1;
//      c.print();
    }
    p--;
    c = c.matrix_pow(p);
//  c.print();
    a = a * c;
//  a.print();
    printf("%d\n", a.m[1][n * 3]);
}