考点：卡特兰数

A_i

给定四个正整数 a,b,c,d ，满足 a，下列式子成立：

• ad+bc

所以，衍生到 2n 个数的排列，上述结论成立。

对于每对配对的数对 (A_i,C_i) ， 可以看作一对”括号“，有 2^n 种方案通过交换左右括号中的数，有 n! 种方案通过排列数对出现的顺序，然后再乘上 cal_n ( n 对括号时的卡特兰数)，就是满足最低瑕疵的方案数。

所以失误率为: $$ \frac{2n!-2^nn!cal_n}{2n!} $$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
using ll = long long;
#define N 200000
const int mod = 998244353;
int cal[N + 10];
int qpow(int x, int y) {
    int rs = 1;
    while (y) {
        if (y & 1) rs = rs * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return rs;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    cal[0] = 1;
    for (int i = 1; i <= N; i++) {
        cal[i] = (4 * i - 2) * cal[i - 1] % mod * qpow(i + 1, mod - 2) % mod;
    }

    int num = cal[n] * qpow(2, n) % mod;

    for (int i = 1; i <= n; i++) {
        num = num * i % mod;
    }

    int sum = 1;
    for (int i = 1; i <= 2 * n; i++) {
        sum = sum * i % mod;
    }

    int ans = ((sum - num) % mod + mod) % mod * qpow(sum, mod - 2) % mod;
    cout << ans;

    return 0;
}