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

CPP

#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;
}

题解：P11870 找数

文章操作

Solution

前言

思路

Code

相关推荐

评论

题解：P11870 找数