题解：P11870 找数

· · 题解

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