Bỏ qua

DP của DP

tác giả: Hope666666

Giới thiệu

Bài viết này sẽ giới thiệu tư tưởng DP lồng DP (DP lồng DP) và thông qua hai ví dụ để minh họa cách áp dụng nó vào các bài toán cụ thể.

Tư tưởng

Cái gọi là "DP lồng DP" thực chất chỉ việc trong quá trình quy hoạch động, ta trừu tượng hóa quá trình giải một bài toán con (thường là một DP) thành một máy tự động (DFA), sau đó thiết kế một lớp DP mới dựa trên máy tự động này.

Kỹ thuật này chủ yếu được áp dụng cho lớp bài toán đếm dãy, xác suất hoặc kỳ vọng. Một bài toán điển hình có cấu trúc như sau:

  • Cho bảng chữ cái \(\Sigma\) và một tập hợp các "dãy hợp lệ" độ dài \(n\) trên đó là \(A \subseteq \Sigma^n\). Tùy vào bảng chữ cái, dãy có thể là chuỗi nhị phân, chuỗi số, dãy trạng thái, v.v.
  • Đối với mỗi dãy cụ thể \(s \in \Sigma^n\), có thể dùng quy hoạch động để kiểm tra xem nó có hợp lệ hay không (tức là \(s \in A\)), tính trọng số của nó hoặc tìm các giá trị liên quan.
  • Cuối cùng, chúng ta muốn thống kê số lượng tất cả các dãy trong tập \(A\), tổng trọng số, giá trị kỳ vọng, v.v.

Lúc này, việc liệt kê tất cả các dãy là không khả thi. Do đó, chúng ta cân nhắc trừu tượng hóa quá trình "kiểm tra một dãy có hợp lệ hay không" (tức là DP lớp trong) thành một máy tự động hữu hạn đơn định (DFA). Thông thường, đối với dãy \(s \in \Sigma^n\) cố định, hàm trạng thái của DP lớp trong có thể biểu diễn là \(g(i, x; s)\), tức là đã xử lý xong tiền tố độ dài \(i\) của dãy \(s\), và giá trị của một đại lượng nào đó khi các thành phần trạng thái khác là \(x\). Tương ứng, phương trình chuyển trạng thái của DP lớp trong là:

\[ g(i,\cdot;s) = G(g(i-1,\cdot;s),s_i). \]

Nói cách khác, hàm \(g(i, \cdot; s)\) được xác định duy nhất bởi hàm \(g(i-1, \cdot; s)\) trước đó và ký tự hiện tại \(s_i\). Nếu coi hàm \(g(i, \cdot; s)\) là một trạng thái của máy tự động, thì phương trình chuyển trạng thái của DP lớp trong sẽ đưa ra phép chuyển trạng thái của máy tự động. Do đó, máy tự động \((Q, \Sigma, \delta, q_0, F)\) tương ứng với DP lớp trong có cấu trúc như sau:

  • Tập hợp trạng thái \(Q\) là tập hợp tất cả các hàm \(g(i, \cdot; s)\) khả dĩ tương ứng với các \(s \in \Sigma^n\) và \(i = 0, 1, \dots, n\);
  • Hàm chuyển \(\delta: Q \times \Sigma \to Q\) chính là hàm \(G\) trong phương trình chuyển trạng thái của DP lớp trong;
  • Trạng thái bắt đầu \(q_0\) thường là hiển nhiên, tức là trạng thái ban đầu của DP lớp trong;
  • Tập hợp trạng thái chấp nhận \(F\) tương ứng với tất cả các dãy hợp lệ \(s \in A\).

Bản thân hàm \(g(i, \cdot; s)\) có thể khá phức tạp, vì vậy khi xử lý các bài toán cụ thể, thường cần thực hiện nén trạng thái hoặc kết hợp với các kỹ thuật tối ưu hóa DFA để nén không gian trạng thái. Đây cũng là lý do chính khiến DP lồng DP có thể giảm đáng kể độ phức tạp về thời gian và không gian so với DP vét cạn.

Sau khi trừu tượng hóa DP lớp trong thành DFA, ta có thể thiết kế một DP mới trên DFA này để giải quyết bài toán gốc, gọi là DP lớp ngoài. Để thuận tiện, lấy bài toán đếm đơn giản làm ví dụ. Hàm trạng thái của DP lớp ngoài được định nghĩa là \(f(i, q)\), tức là số lượng tiền tố độ dài \(i\) dẫn đến trạng thái \(q \in Q\) trong DFA. Phương trình chuyển trạng thái của nó là:

\[ f(i,q) = \sum_{c\in\Sigma}\sum_{q'\in Q:\delta(q',c)=q} f(i-1,q'). \]

Trạng thái bắt đầu đương nhiên là \(f(0, q_0)\), và đáp án cuối cùng thường có thể tính toán đơn giản từ \(\{f(n, q): q \in F\}\). DP lớp ngoài thực chất là một trường hợp đặc biệt của DP trên DAG.

Ví dụ

Hai ví dụ tiếp theo sẽ giải thích chi tiết cách làm chung của DP lồng DP.

Ví dụ 1

Hero meet devil

Cho một xâu \(S\) có bảng chữ cái là ACGT, và \(|S| \le 15\). Với mỗi \(0 \le i \le |S|\), hãy tìm xem có bao nhiêu xâu \(T\) độ dài \(m\) trên bảng chữ cái ACGT sao cho độ dài dãy con chung dài nhất của nó với \(S\) bằng \(i\).

Lời giải

Đầu tiên ta nghĩ đến một DP: Gọi \(f_{i,j}\) là số phương án cho xâu \(T\) độ dài \(i\) có độ dài dãy con chung dài nhất với \(S\) là \(j\). Nhưng cách này không chuyển trạng thái được, vấn đề chính là ta không biết dãy con chung dài nhất đó ứng với những ký tự nào.

Xét quá trình tìm dãy con chung dài nhất (LCS) thông thường. Gọi \(g_{i,j}\) là độ dài LCS của \(i\) ký tự đầu của \(T\) và \(j\) ký tự đầu của \(S\), ta có:

\[ g_{i,j} = \max\{g_{i-1,j},g_{i,j-1},g_{i-1,j-1}+[T_i=S_j]\}. \]

Ta nhận thấy rằng, với một giá trị \(i\), chỉ cần ghi lại giá trị của từng vị trí trong mảng một chiều \(g_i\) là có thể duy trì chính xác trạng thái LCS của \(S\) và \(i\) ký tự đầu của \(T\). Vì độ dài \(S\) chỉ tối đa 15, tư tưởng này là khả thi.

Vì vậy, thiết lập lại trạng thái \(f_{i,x}\) là số phương án cho xâu \(T\) độ dài \(i\) có trạng thái mảng DP của \(S\) (chính là \(g_i\)) là \(x\). DP này có vẻ có rất nhiều trạng thái, tuy nhiên ta thấy \(g_{i,j} - g_{i,j-1} \in \{0, 1\}\), nên có thể duy trì mảng hiệu phân (difference array) của \(g_i\), số trạng thái sẽ là \(2^{|S|}\).

Bây giờ suy nghĩ cách chuyển trạng thái. Dễ thấy nếu biết mảng \(g_i\) và biết \(T_{i+1}\), ta có thể thông qua chuyển trạng thái LCS thông thường (phương trình DP nêu trên) để tìm ra \(g_{i+1}\). Do đó, LCS thông thường trở thành DP lớp trong hỗ trợ chuyển trạng thái cho \(f\).

Vì vậy, ta duyệt qua \(T_{i+1}\), tính toán trạng thái \(x'\) sau khi chuyển từ \(x\), rồi cộng \(f_{i,x}\) vào \(f_{i+1,x'}\). Cuối cùng, ta ghi lại \(\textit{ans}_i\) là đáp án cho độ dài LCS bằng \(i\), duyệt qua mỗi trạng thái \(S\), cộng \(f_{m,S}\) vào \(\textit{ans}_{\operatorname{popcount}(S)}\).

Mã tham khảo 
 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
84
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 100;

int T, a[MAXN + 1], h[MAXN + 1];
int g[MAXN + 1], m, n;
int nxt[1 << 16]
       [4];  // 状态转移表：nx[mask][ch] 表示 mask 状态下追加 ch 后的新状态
int f[1001]
     [1 << 16];  // DP 数组：f[i][mask] 表示长度为 i，处于状态 mask 的方案数
int ans[MAXN +
        1];  // 最终答案：ans[i] 表示长度为 m 时，包含 i 个匹配位置的方案数

void add(int &x, int y) { x = (x + y) % MOD; }

int calc(int mask, int x) {  // 给定当前 mask 状态和当前字符
                             // x（0~3），返回新状态
  int res = 0;
  for (int i = 0; i < n; ++i) g[i + 1] = g[i] + ((mask >> i) & 1);

  for (int i = 1; i <= n; ++i) {
    if (a[i] == x)
      h[i] = g[i - 1] + 1;
    else
      h[i] = max(h[i - 1], g[i]);
  }

  for (int i = 1; i <= n; ++i)
    if (h[i] > h[i - 1]) res |= (1 << (i - 1));

  return res;
}

int popcount(int x) {  // 计算 mask 中有多少个 1（即匹配了多少位置）
  int res = 0;
  while (x) {
    res += x & 1;
    x >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> T;
  while (T--) {
    string S;
    cin >> S >> m;
    n = S.length();

    memset(f, 0, sizeof(f));
    memset(ans, 0, sizeof(ans));
    memset(a, 0, sizeof(a));

    for (int i = 0; i < n; ++i) {
      if (S[i] == 'A') a[i + 1] = 0;
      if (S[i] == 'C') a[i + 1] = 1;
      if (S[i] == 'G') a[i + 1] = 2;
      if (S[i] == 'T') a[i + 1] = 3;
    }

    int lim = (1 << n);
    for (int i = 0; i < lim; ++i)
      for (int j = 0; j < 4; ++j) nxt[i][j] = calc(i, j);

    f[0][0] = 1;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < lim; ++j)
        if (f[i][j])
          for (int k = 0; k < 4; ++k) add(f[i + 1][nxt[j][k]], f[i][j]);

    for (int i = 0; i < lim; ++i) add(ans[popcount(i)], f[m][i]);

    for (int i = 0; i <= n; ++i) cout << ans[i] << '\n';
  }

  return 0;
}

Ví dụ 2

[ZJOI2019] 麻将 (Mạt chược)

Giả sử mạt chược có \(n\) loại quân, mỗi loại có 4 quân. Định nghĩa một "bộ" (mianzi) là ba quân có giá trị liên tiếp \(i, i+1, i+2\) (chi/shunzu) hoặc ba quân cùng giá trị \(i, i, i\) (pơ/kezu), một "cặp" (duizi) là hai quân cùng giá trị \(i, i\). Một dãy quân mạt chược được gọi là "ù" (hu) khi và chỉ khi nó (coi như một đa tập) có thể chia thành bốn bộ và một cặp, hoặc bảy cặp khác nhau. Cho trước 13 quân, hỏi kỳ vọng cần bốc thêm bao nhiêu quân nữa để thỏa mãn điều kiện tồn tại một dãy con "ù".

Lời giải

Trước hết, đối với một bộ bài, ta chỉ cần quan tâm đến số lượng mỗi loại quân mà không cần để ý đến thứ tự của chúng. Do đó, với bất kỳ tiền tố nào của bộ bài, ta đều có thể chuyển nó thành một dãy độ dài \(n\), mỗi vị trí có giá trị từ \(0 \sim 4\). Ban đầu, nếu số lượng quân thứ \(i\) là \(a_i\), tương đương với việc giới hạn giá trị \(x_i\) tại vị trí thứ \(i\) trong dãy nằm trong đoạn \([a_i, 4]\). Lưu ý, dãy sau khi chuyển đổi không xét đến thứ tự bốc quân, nhưng dãy mạt chược trong đề bài thì có xét thứ tự.

Gọi \(X\) là số lần bốc quân tối thiểu để có thể "ù". Việc tính trực tiếp kỳ vọng \(\mathbf E[X]\) khá khó khăn, ta cân nhắc chuyển đổi như sau. Gọi \(h_i\) là số lượng dãy gồm \(i\) quân bốc thêm mà chưa ù. Vì trong dãy mạt chược tương ứng, \(i\) quân này chắc chắn đứng trước \((4n-13-i)\) quân còn lại, nhưng thứ tự giữa \(i\) quân này và thứ tự giữa các quân còn lại là bất kỳ, nên số lượng dãy mạt chược bốc \(i\) quân mà chưa ù là:

\[ h_i \cdot i!(4n-13-i)!. \]

Vì tổng số dãy mạt chược là \((4n-13)!\), nên xác suất bốc \(i\) quân mà chưa ù là:

\[ \mathbf P[X>i] = \dfrac{h_i\cdot i!(4n-13-i)!}{(4n-13)!}. \]

Sử dụng công thức tổng đuôi (tail sum formula), ta có kỳ vọng cần tìm:

\[ \mathbf E[X] = \sum_{i=0}^\infty\mathbf P[X>i] = 1 + \sum_{i=1}^{4n-13}\dfrac{h_i\cdot i!(4n-13-i)!}{(4n-13)!}. \]

Đến đây, bài toán chuyển thành cách tính \(h_i\). Ta sử dụng phương pháp DP lồng DP.

Đầu tiên xét DP lớp trong, tức là dùng DP để kiểm tra một dãy (sau chuyển đổi) có tương ứng với một bộ bài "ù" hay không. Trường hợp bảy cặp khá dễ, trọng tâm là hình thức "ù" thứ nhất. Để làm việc này, gọi \(g_{0/1,i,j,k}\) là số lượng bộ tối đa sau khi xử lý xong \(i\) loại quân đầu tiên, còn thừa \(j\) nhóm \((i-1, i)\) và \(k\) quân \(i\), và đã có/chưa có cặp (tương ứng \(1/0\)). Nếu thực hiện DP trên một dãy, cuối cùng \(g_{1,n}\) chứa một số lớn hơn hoặc bằng 4 thì dãy đó là "ù".

Chuyển trạng thái của DP này khá phức tạp. Ta chia làm hai bước. Bước 1, xét chuyển trạng thái cho \(g_{0/1,i}\). Điều này tương đương với việc nếu thêm \(x_i\) quân loại \(i\) vào bộ bài hiện tại nhưng không tạo cặp mới, số lượng bộ sẽ thay đổi thế nào. Hiển nhiên, nếu muốn sau khi thêm \(x_i\) quân loại \(i\) sẽ có \(\ell\) bộ dây (shunzu), \(j\) nhóm \((i-1, i)\) và \(k\) quân \(i\) riêng lẻ, thì ta nên chuyển từ \((g_{0/1,i-1})_{\ell,j}\) sang (lựa chọn này tránh lãng phí nhất), và dùng số quân còn lại \((x_i-\ell-j-k)\) để tạo ra nhiều bộ ba (kezu) nhất có thể. Liệt kê mọi khả năng, ta có phương trình:

\[ \tilde G(g_{0/1,i-1}, x_i)_{j,k} = \max\left\{(g_{0/1,i-1})_{\ell,j} + \ell + \left\lfloor\dfrac{x_i-\ell-j-k}{3}\right\rfloor:\ell+j+k\le x_i\right\}. \]

Bước 2, xét trường hợp cần tạo cặp. Khi thêm \(x_i\) quân loại \(i\), có ba loại chuyển trạng thái:

  • Chuyển từ \(g_{0,i-1}\) thêm \(x_i\) quân sang \(g_{0,i}\);
  • Chuyển từ \(g_{1,i-1}\) thêm \(x_i\) quân sang \(g_{1,i}\);
  • Nếu \(x_i \ge 2\), chuyển từ \(g_{0,i-1}\) thêm \(x_i-2\) quân sang \(g_{1,i}\).

Từ đó, ta có toàn bộ các phép chuyển từ \(g_{i-1}\) thêm \(x_i\) quân để được \(g_i\).

Giải quyết xong chuyển trạng thái DP lớp trong, ta có thể xây dựng máy tự động ù mạt chược. Các phép chuyển của máy tự động chính là các phép chuyển DP lớp trong nêu trên, đồng thời cần cân nhắc cách biểu diễn mỗi trạng thái. Mỗi trạng thái tương ứng với một bộ giá trị khả dĩ của \(g_i\). Nó có ba chiều \((0/1, j, k)\). Vì các giá trị \(j\) và \(k\) dùng để tạo bộ dây trong tương lai, mà ba bộ dây giống nhau luôn có thể chuyển thành ba bộ ba, nên chỉ cần xét nhu cầu tạo không quá 2 bộ dây giống nhau, mỗi loại quân chỉ cần giữ lại không quá 2 quân, tức \(j, k \in \{0, 1, 2\}\). Do đó, \(g_i\) có thể biểu diễn bằng mảng \(2 \times 3 \times 3\). Ngoài ra, để duy trì hình thức "ù" bảy cặp, cần thêm một biến đếm cho mỗi trạng thái để biểu thị số cặp tối đa hiện có.

Mỗi phần tử trong mảng \(g_i\) có thể nhận giá trị trong \(\{-\infty\} \cup \mathbf N\), nhưng vì số bộ \(\ge 4\) là đã "ù", nên có thể giới hạn mỗi phần tử không quá 4. Vì một dãy đã "ù" thêm bất kỳ quân nào vẫn là "ù", ta có thể dùng tư tưởng tối thiểu hóa DFA để nén tất cả các trạng thái "ù" thành một trạng thái duy nhất. Do đó, đối với trạng thái chưa "ù", thực tế mỗi vị trí chỉ cần xét giá trị trong \(\{-\infty\} \cup \{0, 1, 2, 3\}\). Khi cài đặt, \(-\infty\) dùng \(-1\).

Mặc dù vậy, số lượng trạng thái khả dĩ vẫn rất lớn, tổng cộng \(1 + 7 \times 5^{18}\). Liệt kê chúng là không thực tế. Thực tế, đại đa số các khả năng này không thực sự xuất hiện trong một máy tự động "ù". Để tránh xét các trạng thái không tồn tại, ta dùng tư tưởng BFS, bắt đầu từ trạng thái ban đầu, mở rộng từng bước cho đến khi dừng ở trạng thái "ù". Máy tự động thu được có \(N = 2092\) trạng thái.

Cuối cùng, xét DP trên máy tự động (DP lớp ngoài). Gọi \(f_{i,j,k}\) là số lượng dãy đã xử lý đến loại quân thứ \(i\), bốc tổng cộng \(j\) quân, và đang ở trạng thái thứ \(k\) trên máy tự động. Khi chuyển trạng thái, duyệt số quân bốc thêm \(0 \le t \le 4-a_i\) (\(a_i\) là số quân loại \(i\) đã có trong 13 quân ban đầu), nhân số dãy trước đó với số cách chọn \(t\) quân từ \(4-a_i\) quân là \(\dbinom{4-a_i}{t}\), rồi cộng dồn lại. Một cách hình thức:

\[ f_{i+1,j+t,k'} = \sum_{t=0}^{4-a_i}\dbinom{4-a_i}{t}f_{i,j,k}. \]

Trong đó \(k' = \delta(k, a_i+t)\) là trạng thái sau khi thêm \(a_i+t\) quân vào trạng thái \(k\). Sau khi kết thúc DP lớp ngoài, ta có thể tính được số lượng dãy bốc \(i\) quân mà vẫn chưa "ù":

\[ h_i = \sum_{j=1}^N f_{n,i,j}. \]

Thay vào biểu thức kỳ vọng ở trên để được kết quả.

Mã tham khảo 
  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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;

const int N = 100, M = 400, mod = 998244353;

int n, m, a[N + 5], fact[M + 5], inv[M + 5];

inline int C(int x, int y) {
  return 1LL * fact[x] * inv[y] % mod * inv[x - y] % mod;
}

class HuAutomation {  // 胡牌自动机
 private:
  class Mat {
   private:
    int f[3][3];

   public:
    Mat() {
      for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++) f[i][j] = -1;
    }

    int* operator[](const int& x) { return f[x]; }

    inline bool operator==(Mat x) const {
      for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
          if (f[i][j] != x[i][j]) return 0;
      return 1;
    }

    inline bool operator<(Mat x) const {
      for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
          if (f[i][j] != x[i][j]) return f[i][j] < x[i][j];
      return 0;
    }

    inline bool Check() {
      for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
          if (f[i][j] > 3) return 1;
      return 0;
    }

    inline void Upd(Mat x, int t) {
      // 将已有矩阵 x 的值更新到当前矩阵中，模拟加入 t 张当前牌后的状态
      for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
          if (x[i][j] != -1)
            for (int k = 0; k < 3 && i + j + k <= t; k++)
              f[j][k] = max(f[j][k], min(i + x[i][j] + (t - i - j - k) / 3, 4));
      // i,j,k,(t-i-j-k)
      // 表示分别枚举用于拼面子、用于保留(i-1,i)、用于保留i和直接拼面子的牌数
      //  更新时限制最多 4 个对子
    }
  };

  struct node {
    int t, state[5];
    Mat F[2];

    node() {
      for (int i = 0; i <= 4; i++) state[i] = 0;
      t = 0;
      for (int i = 0; i <= 1; i++) F[i] = Mat();
    }

    inline bool Check() { return t == -1 || t >= 7 || F[1].Check(); }

    node Hu() {
      node x;
      x.t = -1;
      return x;
    }

    bool operator<(const node& x) const {
      if (t == x.t) {
        if (F[0] == x.F[0]) return F[1] < x.F[1];
        return F[0] < x.F[0];
      }
      return t < x.t;
    }

    node operator+(int x) {      // 加上 x 张新牌
      if (Check()) return Hu();  // 胡了直接返回
      node res;
      res.F[0].Upd(F[0], x), res.F[1].Upd(F[1], x);  // 更新
      res.t = t;
      if (x > 1) res.F[1].Upd(F[0], x - 2), ++res.t;
      if (res.Check()) res = Hu();  // 判断是否胡了
      return res;
    }
  } A[2100];

  map<node, int> mp;

  inline int Get(node x) {
    if (mp.count(x)) return mp[x];
    mp[x] = ++tot;
    A[tot] = x;
    return tot;
  }

  inline void Expand(int x) {
    // 构建状态转移图：
    // 对于当前状态 A[x]，尝试加入 0~4 张同种牌，得到 5 个新状态
    for (int i = 0; i <= 4; i++) A[x].state[i] = Get(A[x] + i);
  }

  inline node Hu() {
    node x;
    x.t = -1;
    return x;
  }

  inline node Emp() {
    node x;
    x.F[0][0][0] = 0;
    return x;
  }

 public:
  int tot, f[N + 5][M + 5][2100];

  inline void Build() {
    A[1] = Emp(), A[2] = Hu();  // 状态1是初始合法状态，2 是胡牌状态
    mp[A[1]] = 1, mp[A[2]] = 2;
    tot = 2;
    Expand(1);
    for (int i = 3; i <= tot; i++)
      Expand(i);  // 枚举所有可达状态，构建状态图（因为 2
                  // 是胡牌状态所以不需要拓展）
  }

  void DP() {
    f[0][0][1] = 1;
    for (int i = 1; i <= n; i++)
      for (int j = m; j >= 0; j--)
        for (int k = 1; k <= tot; k++)
          if (f[i - 1][j][k])
            for (int t = 0; t <= 4 - a[i]; t++)
              // 枚举这张牌能加多少个（不能超过4，总共已有a[i]个），做组合转移
              (f[i][j + t][A[k].state[a[i] + t]] +=
               1LL * f[i - 1][j][k] * C(4 - a[i], t) % mod) %= mod;
  }
} Hfu;

inline long long qpow(long long x, int y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return res;
}

void init(int n) {
  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
  inv[n] = qpow(fact[n], mod - 2);
  for (int i = n - 1; i >= 0; i--) inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int ans = 0;
  Hfu.Build();  // 状态图构建
  cin >> n;
  for (int i = 1; i <= 13; i++) {
    int x, y;
    cin >> x;
    cin >> y;
    ++a[x];
  }
  m = (n << 2) - 13;
  init(m);
  Hfu.DP();

  for (int i = 1; i <= m; i++) {
    (ans += 1LL * Hfu.f[n][i][1] * fact[i] % mod * fact[m - i] % mod) %= mod;
    for (int j = 3; j <= Hfu.tot; j++)  // 因为 2 节点是胡牌节点所以不统计
      (ans += 1LL * Hfu.f[n][i][j] * fact[i] % mod * fact[m - i] % mod) %= mod;
    // f[i][j][k]：表示处理到第 i 张牌，共摸了 j 张牌，走到了胡牌自动机上的 k
    // 号节点的方案数 每个方案乘以 i!(用于排列这 i 张) × (m - i)!
    // (剩下的牌排列)，求和后取模
  }

  cout << (1LL * ans * inv[m] + 1) % mod;
  // 最终答案乘上 inv[m] 是除以 m!，即去掉总排列数，最后 +1 是 dp 的定义是摸完 i
  // 张还没有胡
  return 0;
}

Bài tập

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply