自动搬运

查看原文

来自洛谷，原作者为

	Na1L0n9 壶关条件（一周未回关请私信）：红紫名，有大于4级钩，我的朋友，三选一||AquaDaMean1e

搬运于2025-08-24 23:10:58，当前版本为作者最后更新于2025-03-16 18:44:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

前言

最后 5min 想出了解法然后没打完，写篇题解弥补遗憾。

思路

得到序列 $p$ 后，我们对于第 $i$ 位的数，把它的值加上 $i$。因为奇数一定在奇数位上，偶数一定在偶数位上，所以经过修改后的序列 $p$ 一定是一个全偶序列。显然，这个全偶序列的元素会在 $\left[ 1, n+m \right]$ 中分布，问题转化为：

从 $\left[ 1, n+m \right]$ 中选出 $m$ 个偶数，求方案数。

这就是一个简单的排列组合问题。

$ans=C_{\left\lfloor \frac{n + m}{2} \right\rfloor}^{m}$

Code

#include <bits/stdc++.h>
#define Write ios::sync_with_stdio(0);
#define by cin.tie(0);
#define AquaDaMean1e cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6 + 10;
const int MOD = 998244353;
ll n, m, fac[N], inv[N];
int main() {
	Write by AquaDaMean1e
	cin >> n >> m;
	n = (n + m) / 2;
	inv[0] = inv[1] = fac[0] = 1ll;
	for (ll i = 2; i <= n; i++) {
		inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
	}
	for (int i = 1; i <= n; i++) {
		fac[i] = (fac[i - 1] * i) % MOD;
		inv[i] = (inv[i - 1] * inv[i]) % MOD;
	}
	cout << fac[n] * inv[m] % MOD * inv[n - m] % MOD;
	return 0;
}