题解 洛谷 U327217 寻找千泷の小翼龙

本题题面

原题（本题由该题数据加强而来）：

USACO Training 6.1.1 Postal Vans

Tiring of their idyllic fields, the cows have moved to a new suburb. The suburb is a rectangular grid of streets with a post office at its Northwest corner. It has four avenues running East-West and $n(1\le n\le 10^{18})$ streets running North-South.

For example, the following diagram shows such a suburb with $n=5$ streets, with the avenues depicted as horizontal lines, and the post office as a dark blob at the top-left corner:

Each day the postal van leaves the post office, drives around the suburb and returns to the post office, passing exactly once through every intersection (including those on borders or corners). The executives from the post company want to know how many distinct routes can be established for the postal van (of course, the route direction is significant in this count).

For example, the following diagrams show two such routes for the above suburb:

As another example, the following diagrams show all the four possible routes for a suburb with $n=3$ streets:

Write a program that will determine the number of such distinct routes given the number of streets.

INPUT FORMAT

Line 1: Two integers, n, p

SAMPLE INPUT：

1
4 32767

OUTPUT FORMAT

Line 1: A single integer that tells how many possible distinct routes corresponding to the number of streets given in the input, mod p;

SAMPLE OUTPUT:

1
12

简要题意：

给定一个$4\times n$的格子（按照格点计数），从左上角出发沿格子遍历所有格点后再返回起点，要求每个点只遍历一次，计算合法方案的总数 $mod$ $p$ 的值

策略分析：

看到方案数，我们合理地想到了动态规划，而看到数据范围和动态规划，我们合理地想到了矩阵加速。设 $f_i$ 为前 $i$ 列中第 $i$ 列中总的方案数。大家小时候应该都玩过拼管子吧，就那种各种各样形状的管子可以组合成不同的形状，那么本题就是要用类似的方法。

到达南北方向 $1,2$ 路口的方案只有 $2$ 种，我们将管子如下摆放：


到达南北方向 $1,4$ 路口方案有 $7$ 种，但最后两种等价算作一种：








由此我们可以推出状态转移方程，即：
$$f_i=2f_{i-1}+2f_{i-2}-2f_{i-3}+f_{i-4}$$

对于这种方法和递推方程正确性的证明参见阿蒋大佬的blog

得到了状态转移方程我们就可以得到转移矩阵 $M$ 了,
$$M=\begin{vmatrix}
2& 2& -2& 1\
1& 0& 0& 0\
0& 1& 0& 0\
0& 0& 1& 0
\end{vmatrix}$$

我们充分发扬人类智慧，通过大脑和手求得 $f_1=0,f_2=2,f_3=4,f_4=12$

剩余部分显然没有难度了，直接矩阵加速就可以了，于是我们做完了，下面是 $AC$ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define clear(q) memset(q.m, 0, sizeof(q.m))
#define LL long long
using namespace std;

namespace SHAWN {
    LL n, p;
    struct mat { LL m[4][4]; };
    mat operator* (const mat &x, const mat &y) {
        mat ans;
        clear(ans);
        for (int i = 0; i < 4; ++i) {
            for (int k = 0; k < 4; ++k) {
                if (x.m[i][k]) {
                    for (int j = 0; j < 4; ++j) {
                        ans.m[i][j] = ((ans.m[i][j] + (x.m[i][k] * y.m[k][j])) % p + p) % p; 
                    }
                }
            }
        } 
        return ans;
    }
    mat qpow(mat a, LL b) {
        mat z;
        clear(z);
        for (int i = 0; i < 4; ++i) { z.m[i][i] = 1; }
        while (b) {
            if (b & 1) { z = z * a; }
            a = a * a; b >>= 1;
        }
        return z;
    }
    int work()
    {
        cin >> n >> p;
        if (n <= 4) {
            switch (n) {
                case 1 : cout << "0\n"; break;
                case 2 : cout << "2\n"; break;
                case 3 : cout << "4\n"; break;
                case 4 : cout << "12\n"; break;
                default : break;
            }
            return 0;
        }
        mat a;
        clear(a);
        a.m[0][0] = 2; a.m[0][1] = 2; a.m[0][2] = -2; a.m[0][3] = 1;
        a.m[1][0] = 1; a.m[2][1] = 1; a.m[3][2] = 1;
        mat z = qpow(a, n - 4);
        LL ans = ((z.m[0][0] * 12 + z.m[0][1] * 4 + z.m[0][2] * 2) % p + p) % p;
        cout << ans << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

说些什么吧！

twikoo