Card Game

链接：https://ac.nowcoder.com/acm/contest/120561/B 来源：牛客网

题目概述 我们有 2n 张牌，是 1 到 2n 的一个排列。小苯和小红各拿 n 张。 游戏规则：每次比双方当前第一张牌，数字大的得1分并弃掉这张牌，小的不动，一方没牌则结束。 小苯可以任意重排自己的牌，目标是最大化自己的得分，问有多少种重排方式能达到这个最高分。 思路分析 通过观察可知，只有小苯的某张牌 > 小红对应的那张牌时，他才能得分，而小红的牌的顺序是固定的。游戏过程是“对齐比较”：小苯的第 1 张对小红第 1 张，胜则小苯第 1 张移除，小红第 1 张保留（只因输了牌不弃）；不胜则小苯第 1 张被消耗掉（被对手更大的牌压住）。所以小苯应该用自己恰好能赢的牌去赢，避免浪费大牌。 总而言之，实际上，这个游戏等价于：小苯的每张牌只能和它遇到的第一个能赢的红牌对决，并且赢得那张红牌会被立即移除。 所以我们设 bmin 为小红手牌中的最小值。小苯所有大于等于 bmin 的牌，一定可以得分（并且可以安排得一分不丢）；小苯所有小于 bmin 的牌，无论如何都不得分。 因此，我们设 x = 小苯手牌中小于 bmin 的数量（必败牌）；设 y = 小苯手牌中大于等于 bmin 的数量（必胜牌）， x + y = n显而易见，而最高得分 = y（所有必胜牌都能得一分），方案数 = 我们可以任意排列这些牌，只要所有必胜牌在顺序中出现在能赢的位置——实际上，只要必败牌和必胜牌内部各自任意排列即可，因为必胜牌永远能找到能赢的红牌（至少最小值那张等着）。 所以方案数 = x! × y!（全排列内部顺序）。 最后题目要求方案数对 998244353 取模，我们每次阶乘都对 998244353 取模以降低复杂度。 输入描述: 每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦10 ^ 5 ) 代表数据组数，每组测试数据描述如下： 第一行输入一个正整数 n(1≦n≦2×10 ^ 5 )，表示两人的卡牌数量。 第二行输入 n 个正整数 a 1,a 2,…,a n(1≦a i≦2×n)，表示小苯的卡牌上的数字。 第三行输入 n 个正整数 b 1,b 2,…,b n(1≦b i≦2×n)，表示小红的卡牌上的数字。 （保证 a 数组和 b 数组共同构成一个长度为 2×n 的排列。） 总结概括 这个问题的难点在于理解“最小值”的决定性作用，如何将看似复杂的顺序博弈问题化简为简单的阶乘乘积。一句话，小红的最小牌是胜负分水岭，必败牌和必胜牌内部随便排，方案数便是两个阶乘乘起来。 C++代码展示如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long T;
	cin>>T;
	for	(long long i=0; i<T; i++) {
		long long s=1;
		long long n;
		cin>>n;
		long long a[n],b[n];
		long long amin;
		amin=a[0];
		for(long long j=0; j<n; j++) {
			cin>>a[j];
		}
		long long bmin;
		cin>>b[0];
		bmin=b[0];
		for(long long j=1; j<n; j++) {
			cin>>b[j];
			if(bmin>b[j]) {
				bmin=b[j];
			}
		}
		long long x=0,y=0;
		for(long long j=0; j<n; j++) {
			if(a[j]<bmin) {
				x++;
			} else {
				y++;
			}
		}
		for(long long j=1; j<=x; j++) {
			s*=j;
			s%=998244353;
		}
		for(long long j=1; j<=y; j++) {
			s*=j;
			s%=998244353;
		}
		cout<<s<<endl;
	}
}