这题非常的神啊。。。蒟蒻来写一篇题解。
Solution
首先考虑如何判定一副牌是否是 "胡" 的。
不要想着统计个几个值 (O(1)) 算，可以考虑复杂度大一点的。
首先先把 (7) 个对子的状态判掉。然后考虑 (4) 个面子和 (1) 个对子的情况。
记录一个 (dp_{i, j,k}) : (i) 表示现在有没有留出对子，(j) 表示现在形如 (i, i - 1) 的牌的多余的个数， (k) 表示现在形如 (i) 的牌对的个数，整个状态表示现在的面子数量。
使用 dp 套 dp, 对于这个 (dp_{i, j, k}) 分别是多少给压缩起来。这个状态以及转移可以 (bfs) 找。发现这个状态数只有 (2092) 个，所以可以通过此题。
Code
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 405;
const int M = 2200;
const int mod = 998244353;
int qpow(int x, int y) {
if(x == 0) return 0;
int res = 1;
for(; y; x = 1ll * x * x % mod, y >>= 1) if(y & 1) res = 1ll * res * x % mod;
return res;
}
int ny(int x) { return qpow(x, mod - 2); }
int n, winid, ans;
int max(int a, int b) { return a > b ? a : b; }
void Max(int &a, int b) { a = max(a, b); }
struct DPAM {
int f[3][3];
void clear() { L(i, 0, 2) L(j, 0, 2) f[i][j] = -1; }
};
DPAM operator + (DPAM aa, int bb) {
DPAM res; res.clear();
L(i, 0, 2) L(j, 0, 2) if(aa.f[i][j] != -1)
L(k, 0, 2) if(bb >= i + j + k) Max(res.f[j][k], min(aa.f[i][j] + i + (bb - i - j - k) / 3, 4));
return res;
}
void FMAX(DPAM &aa, DPAM bb) {
L(i, 0, 2) L(j, 0, 2) Max(aa.f[i][j], bb.f[i][j]);
}
struct node {
int cnt; DPAM dp[2];
void clear() { cnt = 0; dp[0].clear(), dp[1].clear(); }
};
node win() { node res; res.clear(), res.cnt = 114514; return res; }
bool check(node aa) {
if(aa.cnt >= 7) return 1;
L(i, 0, 2) L(j, 0, 2) if(aa.dp[1].f[i][j] >= 4) return 1;
return 0;
}
bool operator < (node aa, node bb) {
L(t, 0, 1) L(i, 0, 2) L(j, 0, 2) if(aa.dp[t].f[i][j] ^ bb.dp[t].f[i][j]) return aa.dp[t].f[i][j] < bb.dp[t].f[i][j];
return aa.cnt < bb.cnt;
}
node operator + (node aa, int bb) {
if(aa.cnt == 114514) return aa;
node res;
res.clear(), res.cnt = aa.cnt + (bb >= 2);
FMAX(res.dp[0], aa.dp[0] + bb);
FMAX(res.dp[1], aa.dp[1] + bb);
if(bb >= 2) FMAX(res.dp[1], aa.dp[0] + (bb - 2));
if(check(res)) return win();
return res;
}
int tot, dp[2][N][M];
map<node, int> mp;
int G[M][5], jc[N], njc[N];
int C(int x, int y) { return 1ll * jc[x] * njc[x - y] % mod * njc[y] % mod; }
void bfs() {
queue<node> q;
node gg;
gg.clear(), gg.cnt = 0, gg.dp[0].f[0][0] = 0;
mp[gg] = ++tot, q.push(gg);
while(!q.empty()) {
node u = q.front(); int id = mp[u];
q.pop();
L(i, 0, 4) {
node v = u + i;
if(!mp.count(v)) {
G[id][i] = mp[v] = ++tot, q.push(v);
if(v.cnt == 114514) winid = tot;
}
else G[id][i] = mp[v];
}
}
}
int cnt[N];
void work() {
dp[0][0][1] = 1;
L(i, 1, n) {
int now = (i & 1);
memset(dp[now], 0, sizeof(dp[now]));
L(j, 1, tot) L(k, 0, (i - 1) * 4) L(t, 0, 4 - cnt[i])
(dp[now][k + t][G[j][t + cnt[i]]] += 1ll * dp[now ^ 1][k][j] * C(4 - cnt[i], t) % mod) %= mod;
}
L(i, 0, n * 4 - 13) L(j, 1, tot) if(j != winid) (ans += 1ll * ny(C(4 * n - 13, i)) * dp[n & 1][i][j] % mod) %= mod;
}
int mian() {
bfs();
scanf("%d", &n);
jc[0] = njc[0] = 1;
L(i, 1, n * 4) jc[i] = 1ll * jc[i - 1] * i % mod, njc[i] = ny(jc[i]);
L(i, 1, 13) {
int x, y;
scanf("%d%d", &x, &y), cnt[x]++;
}
work();
printf("%d
", ans);
return 0;
}