观察：三组相同的顺子可以变成三组刻子，因此不妨令每种顺子的数量小于 \(3\)。
记编号为 \(i\) 的牌有 \(a_i\) 张。考虑确定 \(a\) 后，判定是否和牌。
令 \(f(x, p, q, 0/1)\) 表示用完编号为 \(1 \sim x\) 的牌，有 \(p\) 个 \((x - 1, x, x + 1)\) 的顺子，\(q\) 个 \((x, x + 1, x + 2)\) 的顺子，是否使用雀头，的情况是否可能。其中 \(p, q \in \{0, 1, 2\}\)。
转移时讨论是否在当前位置使用雀头：
- 不使用，\(f(x - 1, p, q, 0/1) \rightarrow f(x, q, (c_x - p - q) \bmod 3, 0/1)\)
- 使用，\(f(x - 1, p, q, 0) \rightarrow f(x, q, (c_x - p - q - 2) \bmod 3, 1)\)
暴力枚举在哪里 \(+1\) 可得到 \(O(n^2)\) 算法。
在此基础上，有三种线性做法。
-
在原来的 DP 的基础上新增一维表示是否已经听牌，记录转移并建图倒推合法听牌位置，常数较大。具体可参考：麻将 加强加强版 题解 by Milkcat
-
尝试在序列上动态 DP，预处理每个位置上的转移矩阵，矩阵乘法预处理前缀后缀，压位后仍有 \(18^2\) 倍常数。（口胡，矩阵比较稀疏，可能可以进一步优化？
-
正着 DP 一遍，倒着 DP 一遍，然后在每个 \(x\) 处将两侧 DP 信息整合，判断能否听牌。常熟较小，喜提最优解。
- 设 \(g(x, p, q, 0/1)\) 表示用完编号为 \(x \sim n\) 的牌，有 \(p\) 个 \((x - 1, x, x + 1)\)，\(q\) 个 \((x - 2, x - 1, x)\)，是否使用雀头，的情况是否可能。
- 假定在 \(x\) 处听牌，枚举使用了 \(p\) 个 \((x - 2, x - 1, x)\)，\(q\) 个 \((x, x + 1, x + 2)\)，讨论雀头位于 \(1 \sim x-1\)，\(x\)，\(x+1 \sim n\) 中哪一部分，判断能否成立。
int n, m, a[MAXN];
bool f[MAXN][3][3][2], g[MAXN][3][3][2];int main() {read(n, m);for (int i = 1, x; i <= m; ++i) read(x), ++a[x];f[0][0][0][0] = 1;for (int x = 1; x <= n; ++x) {for (int p : {0, 1, 2}) for (int q : {0, 1, 2}) for (int v : {0, 1}) {if (!f[x-1][p][q][v]) continue;if (a[x] >= p + q) f[x][q][(a[x]-p-q)%3][v] = 1;if (!v && a[x] >= p + q + 2) f[x][q][(a[x]-p-q-2)%3][1] = 1;}}g[n+1][0][0][0] = 1;for (int x = n; x; --x) {for (int p : {0, 1, 2}) for (int q : {0, 1, 2}) for (int v : {0, 1}) {if (!g[x+1][p][q][v]) continue;if (a[x] >= p + q) g[x][q][(a[x]-p-q)%3][v] = 1;if (!v && a[x] >= p + q + 2) g[x][q][(a[x]-p-q-2)%3][1] = 1;}}int cnt = 0;for (int x = 1; x <= n; ++x) {bool fl = 0;for (int p : {0, 1, 2}) for (int q : {0, 1, 2}) {int t0 = a[x] + 1 - p - q, t1 = a[x] - 1 - p - q;if (t0 >= 0) fl |= f[x-1][p][t0%3][0] && g[x+1][q][t0%3][1] || f[x-1][p][t0%3][1] && g[x+1][q][t0%3][0];if (t1 >= 0) fl |= f[x-1][p][t1%3][0] && g[x+1][q][t1%3][0];if (fl) break;}if (fl) write(x, ' '), ++cnt; }if (!cnt) puts("QAQ");return 0;
}