• 题目描述

小苯正在和小红玩卡牌游戏。游戏中有 2 × 𝑛 2×n 张牌，每张牌上都有一个数字，所有牌的数字恰好构成了一个长度为 2 × 𝑛 2×n 的排列。 游戏最初时， 2 × 𝑛 2×n 张卡牌被恰好平均分成了两组 𝑛 n 张牌，并分别发给了两人，小苯第 𝑖 i 张牌上的数字是 𝑎 𝑖 a i​，而小红第 𝑖 i 张牌上的数字是 𝑏 𝑖 b i​，具体的游戏过程如下： ∙   ∙如果两人之中有一人已经没有牌了，则游戏结束。 ∙   ∙比较两人当前手牌中的最前一张，对应数字大的那一方得一分并将该张牌从自己手牌移除；另一方不得分，手牌也不变。随后进入下一轮。

而现在小苯希望自己的得分尽可能多，为此他在游戏开始前可以任意地重新排列自己的牌，以得到更高的游戏分数。 现在你的任务则是求出，有多少种重新排列（选择不进行重排也是一种方案）的方式，能使得小苯得到他能得到的最高分。由于答案可能很大，请将答案对 998   244   353 998244353 取模后输出。

  • 【名词解释】

长度为 𝑛 n 的排列：由 1 , 2 , … , 𝑛 1,2,…,n 这 𝑛 n 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， { 2 , 3 , 1 , 5 , 4 } {2,3,1,5,4} 是一个长度为 5 5 的排列，而 { 1 , 2 , 2 } {1,2,2} 和 { 1 , 3 , 4 } {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

  • 输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 𝑇 ( 1 ≦ 𝑇 ≦ 1 0 5 ) T(1≦T≦10 5 ) 代表数据组数，每组测试数据描述如下：

第一行输入一个正整数 𝑛 ( 1 ≦ 𝑛 ≦ 2 × 1 0 5 ) n(1≦n≦2×10 5 )，表示两人的卡牌数量。 第二行输入 𝑛 n 个正整数 𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 ( 1 ≦ 𝑎 𝑖 ≦ 2 × 𝑛 ) a 1​,a 2​,…,a n​(1≦a i​≦2×n)，表示小苯的卡牌上的数字。 第三行输入 𝑛 n 个正整数 𝑏 1 , 𝑏 2 , … , 𝑏 𝑛 ( 1 ≦ 𝑏 𝑖 ≦ 2 × 𝑛 ) b 1​,b 2​,…,b n​(1≦b i​≦2×n)，表示小红的卡牌上的数字。 （保证 𝑎 a 数组和 𝑏 b 数组共同构成一个长度为 2 × 𝑛 2×n 的排列。）

除此之外，保证单个测试文件的 𝑛 n 之和不超过 2 × 1 0 5 2×10 5 。

  • 输出描述:

对于每一组测试数据，新起一行输出一个整数，表示小苯重新排列自己卡牌，使得他能得到的最高分的方案数对998244353取模后的值。

  • 题解如下：

根据题意，我们可以清楚的明白游戏性质：小苯可以重新排列自己的牌，所以他的出牌顺序完全可控，显而易见，我们想要解决这道题，必须要先确定小苯的最大得分才可以讨论他的方案数，理解了题意其实再来看这道题就很简单了，为了最大化得分，小苯应该用自己最大的牌去赢小红当前最小的牌，如果小苯没有能赢小红当前最小牌的牌，就输掉这一轮，因此要想知道小苯的最大得分实际上就是要求小苯有多少张牌大于小红的最小牌，那就很简单了，求最小值循环遍历小苯能赢的次数即可。

  • 关于如何求方案数：

现在我们知道最大得分是 k（小苯牌中大于 mn 的数量）。 有多少种排列能达到这个最高分呢？

获胜的排列：k 张大于 mn 的牌必须全部获胜，但它们之间可以任意排列：k! 种方式

失败的排列：剩下的 y = n - k 张牌（都 ≤ mn）会输掉，它们之间也可以任意排列：y! 种方式

所以总方案数 = k! * y!

我当时就是没弄会方案数怎么求所以没能ac这题

  • 代码如下，如有错误感谢指出和纠正
……省略头文件
const int N = 200005;
const int MOD = 998244353;
int fact[N];

void init() {   //阶乘
	fact[0] = 1;
	for (int i = 1; i < N; i++)
		fact[i] = fact[i - 1] * i % MOD;
}

void solve() {
	int i, n;
	cin >> n;
	vi a(n), b(n);
	for (i = 0; i < n; i++)
		cin >> a[i];
	int mn = LONG_LONG_MAX;   //头文件有#define int long long 为了减少代码量没复制头文件
	for (i = 0; i < n; i++) {
		cin >> b[i];
		mn = min(mn, b[i]);
	}
	int k = 0, m;
	for (i = 0; i < n; i++)
		if (a[i] > mn)
			k++;
	cout << fact[k]*fact[n - k] % MOD << endl;
}
signed main() {
	init();
	//vector<vector<int>>a(n,vector<int>(m)); 二维构造
	//cout << fixed << setprecision(10);  固定小数输出
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	cin >> T;
	while (T--) solve();
	return 0;
}