CF Edu 170 E - Card Game

题目大意

题面

有一副牌，共 $n \times m$ 张。每张牌有两个参数：花色和点数。

• 花色编号为 $1 \ldots n$ 。

• 点数编号为 $1 \ldots m$ 。

• 每一种花色和点数的组合都恰好有一张牌。

一张牌 $(a,b)$ 可以打败另一张牌 $(c,d)$ ，当且仅当满足下面两种情况之一：

• $a=1$ 且 $c\ne 1$ 。也就是说，花色 $1$ 是王牌，可以打败任何非王牌花色。

• $a=c$ 且 $b>d$ 。也就是说，同花色里只能用更大的点数去打更小的点数。

两名玩家把整副牌平分。第一名玩家获胜，当且仅当：对第二名玩家的每一张牌，都能选出第一名玩家的一张牌打败它，并且第一名玩家的每张牌最多只用一次。

题目要求统计有多少种分牌方式能让第一名玩家获胜，答案对 $998244353$ 取模。

输入格式

输入一行两个整数 $n,m$ 。

输出格式

输出一个整数，表示合法分牌方式数量。

数据范围

• $1 \le n,m \le 500$

• $m$ 是偶数

样例

Input
1 4
Output
2

Input
2 2
Output
2

Input
3 6
Output
1690

Input
5 4
Output
568

Input
500 500
Output
84693741

思路讲解

一句话

这题先把一个花色内部压成一排 Catalan / ballot 数，再把非王牌花色的“缺口”当成资源消耗做 DP。

关键不变量：花色 $1$ 多出来的牌，必须刚好补完所有非王牌花色内部的缺口。

一个花色为什么像括号序列

先只看一个固定花色，把点数从大到小扫。

• 第一名玩家拿到这张牌，记成左括号。

• 第二名玩家拿到这张牌，记成右括号。

同花色牌只能用高点数打低点数，所以扫到任何一个高点数前缀时，都必须保证这个前缀里第一名玩家的牌数不少于第二名玩家的牌数。

换成括号语言，就是：

任意前缀里，左括号数量不能少于右括号数量。

这就是 Catalan 数最常见的前缀余额模型。

Catalan 数和反射法

如果一个花色里双方各拿 $m/2$ 张，并且完全靠本花色自己匹配，那么合法安排数是：

$$\binom{m}{m/2}-\binom{m}{m/2+1}$$

它来自反射法：所有平衡括号序列一共有 $\binom{m}{m/2}$ 个；不合法序列会在某个位置第一次让前缀余额变成 $-1$ ，把开头到这个位置的括号全部翻转，就会一一对应到左括号多一个的序列，也就是 $\binom{m}{m/2+1}$ 个。

所以合法数就是“全部方案减掉坏方案”。

带缺口的 ballot 数

这题里非王牌花色不一定要自己完全匹配，因为花色 $1$ 可以来救场。

如果某个非王牌花色中，第一名玩家比一半少拿了 $j$ 张，那么：

• 第一名玩家拿了 $m/2-j$ 张。

• 第二名玩家拿了 $m/2+j$ 张。

• 这个花色总量上缺了 $2j$ 张先手牌。

为了不额外消耗更多王牌，这个花色从大到小扫描时，前缀余额最低只能掉到 $-2j$ 。这仍然是 ballot 数，方案数刚好是：

$$dp1[j]=\binom{m}{m/2+j}-\binom{m}{m/2+j+1}$$

这个式子也能用于王牌花色：如果花色 $1$ 中第一名玩家比一半多拿了 $j$ 张，那么它自己内部能匹配，并且最后剩下 $2j$ 张王牌去补其它花色。

状态定义怎么长出来

单个花色已经被压成了 $dp1[j]$ ，后面就不用再记每张牌的具体归属了。

可以定义 $dp2[j]$ 为：处理完若干个花色后，花色 $1$ 还剩 $j$ 份优势没有被用掉的方案数。

这里的 $j$ 表示“多拿了几张的一半资源单位”。真实可补的王牌数量是 $2j$ 。

初始化时，只处理花色 $1$ ：

$$dp2[j]=dp1[j]$$

然后依次处理其它 $n-1$ 个花色。假设当前还剩 $k$ 份优势，当前非王牌花色少拿了 $k-j$ 张，那么处理后就还剩 $j$ 份优势：

$$ndp[j] += dp2[k]\cdot dp1[k-j]$$

也就是代码里的转移：

for (int j = 0; j <= M / 2; ++j) {
    for (int k = j; k <= M / 2; ++k) {
        ndp[j] += dp2[k] * dp1[k - j];
        ndp[j] %= mod;
    }
}

最后必须剩余优势为 $0$ ，因为整副牌要平分，花色 $1$ 多拿的量必须被非王牌少拿的量完全抵消：

ll ans = dp2[0];

复杂度

$m\le 500$ ，所以状态上限只有 $m/2$ 。

• 预处理组合数： $O(m)$ 。

• 单花色贡献： $O(m)$ 。

• 多花色 DP： $O(nm^2)$ 。

• 空间复杂度： $O(m)$ 。

AC 代码

AC 提交链接

源码较长，折叠如下。

展开完整源码

// teamname: Gospel_rock
/**
 * Problem: E. Card Game
 * URL:     https://codeforces.com/contest/2025/problem/E
 * Limits:  2000 ms / 512 MB
 * Author:  Gospel_rock
 * My blog: https://znzryb.com/
 *
 * Powered by cph-ng (https://github.com/langningchen/cph-ng)
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)

using namespace std;

#if 1 && defined(LOCAL)
// clang-format off
// @formatter:off
namespace DBG {
	template<typename T> void debug(T x);
	void debug(bool x);
	void debug(string x);
	template<typename T> void debug(vector<T> v);
	template<typename T, size_t N> void debug(array<T, N> v);
	template<typename T> void debug(set<T> s);
	template<typename T, typename U> void debug(pair<T, U> p);
	template<typename T, typename U> void debug(map<T, U> m);
	template<typename, typename = void> constexpr bool _has_iter_v = false;
	template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
	template<typename T>
	void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
	template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
	template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
	template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
	template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
	template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
	void _dbg() { cerr << endl; }
	template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
// clang-format on
// @formatter:on
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)5e2 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353;  // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

namespace Comb {  // 组合数加逆元，依赖于这个MAXN（初始化）
	vector<ll> frac, infrac;
	int ln = 1;
	bool initialized = false;
	// 在 k=0或者更小的时候 return 1
	inline ll binpow(ll a, ll k) {
		ll res = 1;
		a %= mod;
		while (k > 0) {
			if (k & 1) res = (res * a) % mod;
			a = (a * a) % mod;
			k >>= 1;
		}
		return res;
	}

	void Comb(int n) {
		ln = n;
		frac.assign(n + 5, 1);
		infrac.assign(n + 5, 1);
		for (int i = 1; i <= ln; ++i) {
			frac[i] = (frac[i - 1] * i) % mod;
		}
		infrac[ln] = binpow(frac[ln], mod - 2);
		for (int i = ln - 1; i >= 0; --i) {
			infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
		}
	}

	inline ll CC(ll n, ll k) {
		if (k < 0 || k > n) {
#ifdef LOCAL
			cerr << "CC 组合数传入参数不合法，可能是传入顺序错了\n";
#endif
			return 0;  // Return 0 if k is out of range [0, n]
		}
		if (!initialized) {
			Comb(MAXN);
			initialized = true;
		}
		ll res = frac[n];
		res = (res * infrac[n - k]) % mod;
		res = (res * infrac[k]) % mod;
		return res;
	}

	inline ll PP(ll n, ll k) {
		if (k < 0 || k > n) {
#ifdef LOCAL
			cerr << "PP 排列数传入参数不合法，可能是传入顺序错了\n";
#endif
			return 0;
		}
		if (!initialized) {
			Comb(MAXN);
			initialized = true;
		}
		ll res = frac[n] * infrac[n - k];
		res %= mod;
		return res;
	}
}  // namespace Comb
using namespace Comb;

void Solve() {
	ll N, M;
	cin >> N >> M;
	// i 花色，多取 j 张，内部的数量是多少？(当然，这个多取 j 张，是 A 多取，还是 B 多取，也就是我们一念之间的事情)
	vector<ll> dp1(M / 2 + 2);
	for (int j = 0; j <= M / 2; ++j) {
		dp1[j] = CC(M, M / 2 + j) - CC(M, M / 2 + j + 1);
		dp1[j] %= mod;
	}
	// 在第一个花色多余 j 张的情况下（一开始多取的 ≥ j），处理到 i 花色的时候
	// 总共有的这个情况数量
	vector<ll> dp2 = dp1;
	vector<ll> ndp;
	for (int i = 2; i <= N; ++i) {
		ndp.assign(M / 2 + 2, 0);
		for (int j = 0; j <= M / 2; ++j) {
			for (int k = j; k <= M / 2; ++k) {
				ndp[j] += dp2[k] * dp1[k - j];
				ndp[j] %= mod;
			}
		}
		swap(dp2, ndp);
	}
	// 第一个花色，最后必须是剩余 0 才可以
	ll ans = dp2[0];
	ans %= mod;
	if (ans < 0) ans += mod;
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf);  // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase = 1; testcase <= lT; ++testcase)
	Solve();
	return 0;
}

/*
AC
https://codeforces.com/contest/2025/submission/377246121

*/

心路历程（WA，TLE，MLE……）

卡点：第二维不应该是点数位置

一开始很容易想成 $dp[i][j]$ 表示“处理到第 $i$ 个花色、第 $j$ 张牌”。这个方向的问题是：花色内部一旦处理完，跨花色传递的并不是具体点数位置，而是这个花色消耗了多少王牌资源。

真正要传递的是“花色 $1$ 还剩多少优势”，或者等价地，“非王牌花色累计少拿了多少”。所以第二维应该是资源缺口，不是 rank 下标。

卡点：每一轮 DP 必须清空

处理一个新花色时，ndp 必须从 $0$ 开始。

ndp.assign(M / 2 + 2, 0);

如果写成 ndp = dp2，就相当于允许当前花色不处理，旧状态直接继承，会把方案数多算进去。

卡点：答案不是所有剩余状态求和

如果 $dp2[j]$ 表示花色 $1$ 还剩 $j$ 份优势，那最后只能取 $dp2[0]$ 。

剩余优势大于 $0$ 的状态，表示花色 $1$ 多拿的牌没有被其它花色少拿的牌抵消，整副牌没有平分，不能算合法分配。

附件

暂无。