[ZJOI2019] 麻将

首先发现一个集合怎么判定就不太简单，先考虑判定！

判掉 $\ge 7$ 个对子的情况，考虑另外一种胡牌，设 $f(0/1,j,k)$ 表示此时无 / 有用来胡牌的对子，有 $j$ 个形如 $i-1,i$ 的不完整面子，$k$ 个 $i$ 的单牌，最多能组出多少个面子。其实和 NOI2022 D1T2 那个 dp套dp 题的内层状态设计很像。

判定条件就是存在一个 $f(1,j,k)\ge 4$。

考虑计数。也就是统计选了 $i(i\in [0,4n-13])$ 张牌还没有胡牌的方案数。

考虑 dp套dp，这个可以感性猜测一下，胡牌的时候牌数并不会很多，所以有可能还没胡牌的集合非常少。建出来自动机看看有多少个节点就是。这一步就是爆搜。

先把所有内层 dp 可能达到的状态用 bfs 预处理成一个自动机的模型，外层再套一个 dp：设 $dp(i,j,k)$ 表示考虑完前 $i$ 种牌，现在选了 $j$ 张牌，处在自动机节点 $k$ 上的方案数。转移是简单的，枚举第 $i$ 种牌选了几张，自动机节点跟着转移即可。

时间复杂度大概是 O ( ∣ S ∣ × n 2 ) \mathcal O(|\mathcal S|\times n^2) O(∣S∣×n2)，其中 $\mathcal{S}$ 表示自动机的结点集合。搜出来是 2092 个。确实不多。可以过。

// Problem: P5279 [ZJOI2019]麻将
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5279
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include const int maxn = 405;
const int maxm = 2205;
const int mod = 998244353;void add(int& x, int y) {if((x += y) >= mod)x -= mod;return ;
}void sub(int& x, int y) {if((x -= y) < 0)x += mod;return ;
}int inc(int x, int y) {return (x + y) >= mod ? (x + y - mod) : (x + y);
}int dec(int x, int y) {return (x - y) < 0 ? (x - y + mod) : (x - y);
}int power(int x, int y) {int ans = 1;for(;y;y >>= 1) {if(y & 1)ans = 1ll * ans * x % mod;x = 1ll * x * x % mod;}return ans;
}int fac[maxn], inv[maxn], n;int C(int n, int m) {if(n < 0||m < 0||n < m)return 0;return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}void chkmax(int& x, int y) {if(y > x)x = y;return ;
}struct DPAM {int f[3][3];DPAM() {memset(f, -1, sizeof(f));}void clear() {memset(f, -1, sizeof(f));return ;}DPAM operator + (const int& x) const {DPAM res;for(int i = 0;i <= 2;++ i)for(int j = 0;j <= 2;++ j)if(~ f[i][j])for(int k = 0;k <= 2;++ k)if(x >= i + j + k)chkmax(res.f[j][k], std::min(4, f[i][j] + i + (x - i - j - k) / 3));return res;}
};void Fmax(DPAM& A, DPAM B) {for(int i = 0;i <= 2;++ i)for(int j = 0;j <= 2;++ j)chkmax(A.f[i][j], B.f[i][j]);return ;
}struct node {int cnt;DPAM dp[2];node() {cnt = 0;dp[0].clear();dp[1].clear();}void clear() {return cnt = 0, dp[0].clear(), dp[1].clear(), void();}bool operator < (const node& p) const {for(int k = 0;k < 2;++ k)for(int i = 0;i <= 2;++ i)for(int j = 0;j <= 2;++ j)if(dp[k].f[i][j] ^ p.dp[k].f[i][j])return dp[k].f[i][j] < p.dp[k].f[i][j];return cnt < p.cnt;}
};node win() {node res;res.cnt = 114514;return res;
}bool check(node& x) {if(x.cnt >= 7)return true;for(int i = 0;i <= 2;++ i)for(int j = 0;j <= 2;++ j)if(x.dp[1].f[i][j] >= 4)return true;return false;
}node operator + (const node& A, const int& x) {if(A.cnt == 114514)return A;node res;Fmax(res.dp[0], A.dp[0] + x);Fmax(res.dp[1], A.dp[1] + x);res.cnt = A.cnt + (x >= 2);if(x >= 2)Fmax(res.dp[1], A.dp[0] + (x - 2));if(check(res))return win();return res;
}int tot, dp[2][maxn][maxm], tr[maxm][5], winid, ans, now, cnt[maxn];
std::map<node, int> mp;void bfs() {std::queue<node> q;node res;res.dp[0].f[0][0] = 0;q.emplace(res);mp[res] = ++ tot;while(!q.empty()) {node A = q.front();q.pop();int id = mp[A];for(int i = 0;i <= 4;++ i) {node B = A + i;if(!mp.count(B)) {tr[id][i] = mp[B] = ++ tot;q.emplace(B);if(B.cnt == 114514)winid = tot;}elsetr[id][i] = mp[B];}}return ;
}int main() {scanf("%d", &n);fac[0] = 1;for(int i = 1;i <= 4 * n;++ i)fac[i] = 1ll * fac[i - 1] * i % mod;inv[4 * n] = power(fac[4 * n], mod - 2);for(int i = 4 * n - 1;i >= 0;-- i)inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;bfs();for(int i = 1, x, y;i <= 13;++ i)scanf("%d %d", &x, &y), ++ cnt[x];dp[now = false][0][1] = 1;for(int i = 1;i <= n;++ i) {now ^= true;memset(dp[now], 0, sizeof(dp[now]));for(int j = 1;j <= tot;++ j)for(int k = 0;k <= 4 * (i - 1);++ k)for(int t = 0;t <= 4 - cnt[i];++ t)add(dp[now][k + t][tr[j][t + cnt[i]]], 1ll * dp[now ^ true][k][j] * C(4 - cnt[i], t) % mod);}for(int i = 0;i <= 4 * n - 13;++ i)for(int j = 1;j <= tot;++ j)if(j ^ winid)add(ans, 1ll * power(C(4 * n - 13, i), mod - 2) * dp[now][i][j] % mod);printf("%d\n", ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！