LG P3990 【SHOI2013】 超级跳马 解题报告

地址

看到 $n\le 50,m\le 10^9$ 的数据范围，可以想到矩阵快速幂。不论如何，我们先从 dp 推起。

设 $f(i,j)$ 表示到 $(i,j)$ 的方案数，则

f ( i , j ) = ∑ k = j − 1 − 2 t ≥ 1 , t ∈ N f ( { i − 1 , i , i + 1 } , k ) f(i,j)=\sum_{k=j-1-2t \ge 1,t\in \mathrm N}f(\{i-1,i,i+1\},k) f(i,j)=k=j−1−2t≥1,t∈N∑​f({i−1,i,i+1},k)

（其中 $j\ge 2$）

又

f ( i , j − 2 ) = ∑ k = j − 3 − 2 t ≥ 1 , t ∈ N f ( { i − 1 , i , i + 1 } , k ) f(i,j-2)=\sum_{k=j-3-2t\ge 1,t\in \mathrm N}f(\{i-1,i,i+1\},k) f(i,j−2)=k=j−3−2t≥1,t∈N∑​f({i−1,i,i+1},k)

（其中 $j\ge 4$）

综合以上两式可得

f ( i , j ) = f ( { i − 1 , i , i + 1 } , j − 1 ) + f ( i , j − 2 ) f(i,j)=f(\{i-1,i,i+1\}, j-1)+f(i,j-2) f(i,j)=f({i−1,i,i+1},j−1)+f(i,j−2)

（其中 $j\ge 4$）

注意这些 $j$ 的范围很重要。

这个递推显然是 $O(nm)$ 的，但是我们发现这是一个线性齐次递推，所以可以矩阵处理：

[ f ( 1 , j ) f ( 2 , j ) ⋯ f ( n , j ) f ( 1 , j − 1 ) f ( 2 , j − 1 ) ⋯ f ( n , j − 1 ) ] = A [ f ( 1 , j − 1 ) f ( 2 , j − 1 ) ⋯ f ( n , j − 1 ) f ( 1 , j − 2 ) f ( 2 , j − 2 ) ⋯ f ( n , j − 2 ) ] = A j − 3 [ f ( 1 , 3 ) f ( 2 , 3 ) ⋯ f ( n , 3 ) f ( 1 , 2 ) f ( 2 , 2 ) ⋯ f ( n , 2 ) ]

= A = A^{j-3} ⎣ ⎡​f(1,j)f(2,j)⋯f(n,j)f(1,j−1)f(2,j−1)⋯f(n,j−1)​⎦ ⎤​=A⎣ ⎡​f(1,j−1)f(2,j−1)⋯f(n,j−1)f(1,j−2)f(2,j−2)⋯f(n,j−2)​⎦ ⎤​=Aj−3⎣ ⎡​f(1,3)f(2,3)⋯f(n,3)f(1,2)f(2,2)⋯f(n,2)​⎦ ⎤​

推到 3 是因为 $j\ge 4$ 时才有上面的那个是式子成立。$A$ 是容易构造的。

本题注意特判：根据 $n$ 的不同，初值列向量是不同的；$m$ 需要特判 $m<3$。

时间复杂度 $O(n^3\log m)$。

/*
 * @Author: rijuyuezhu
 * @Date: 2022-07-30 08:05:37
 * @Description: https://www.luogu.com.cn/problem/P3990
 * @Tag: 数学，矩阵，快速幂，DP
*/
#include
#include
#include
using namespace std;
typedef long long ll;
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), tt == ss) ? EOF : *ss++)
ll read() {
   ll x = 0, f = 1; char ch = getchar();
   for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
   for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
   return x * f;
}

const int MAXN = 105;
const int P = 30011;
struct mint {
   int v;
   mint(int v = 0) : v(v) {}
};
int MOD(int v) {return v >= P ? v - P : v;}
mint operator + (mint a, mint b) {return MOD(a.v + b.v);}
mint operator - (mint a, mint b) {return MOD(a.v - b.v + P);}
mint operator * (mint a, mint b) {return a.v * b.v % P;}
int Mat_size;
struct Mat {
   mint A[MAXN][MAXN];
   mint* operator [] (int k) {return A[k];}
   const mint* operator [] (int k)const {return A[k];}
   void clear() {
      for(int i = 1; i <= Mat_size; i++)
         for(int j = 1; j <= Mat_size; j++)
            A[i][j] = 0;
   }
   void unit() {
      for(int i = 1; i <= Mat_size; i++)
         for(int j = 1; j <= Mat_size; j++)
            A[i][j] = (i == j);
   }
};
Mat operator * (const Mat& a, const Mat& b) {
   Mat c; c.clear();
   for(int i = 1; i <= Mat_size; i++)
      for(int k = 1; k <= Mat_size; k++)
         for(int j = 1; j <= Mat_size; j++)
            c[i][j] = c[i][j] + a[i][k] * b[k][j];
   return c;
}
Mat qpow(Mat a, int n) {
   Mat ret; ret.unit();
   for(; n; n >>= 1, a = a * a)
      if(n & 1) ret = ret * a;
   return ret;
}

int n, m;
Mat B, ans;
int main() {
   n = read(), m = read();
   if(m == 1) {
      printf("%d\n", n == 1 ? 1 : 0);
   } else if(m == 2) {
      printf("%d\n", n == 1 || n == 2 ? 1 : 0);
   } else {
      Mat_size = 2 * n; B.clear();
      for(int i = 1; i <= n; i++) {
         B[i][i] = B[i+n][i] = B[i][i+n] = 1;
         if(i > 1) B[i][i-1] = 1;
         if(i < n) B[i][i+1] = 1;
      }
      ans = qpow(B, m-3);
      if(n == 1) printf("%d\n", (ans[n][1] + ans[n][n+1]).v);
      else if(n == 2) printf("%d\n", (2 * ans[n][1] + 2 * ans[n][2] + ans[n][n+1] + ans[n][n+1]).v);
      else printf("%d\n", (2 * ans[n][1] + 2 * ans[n][2] + ans[n][3] + ans[n][n+1] + ans[n][n+2]).v);
   }
   return 0;
}
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83