题解 | [组合数学]圣遗物

概率显然是合法情况数比n的阶乘（涉及数论除法，需求乘法逆元），我的想法是对于选定一个第 个大小的数放第一位，显然，若存在比他小的数得连续递减放，假设有 个，连续比他大的数就得递增放，有 个，总共 个，显然顺序是不能变的，那就预先填好比他小（大）的数放的位置，有组合 个（注意组合数性质，等价于预先填比他大的数），剩下比他大（小）的数显然按顺序排列，所有组合数的 从 到 的总和为 ，用 乘上 的阶乘的逆元即可。

我舍友的想法是，放一个数，再插入一个数的情况有两种，分别插左右（不用管它们的大小关系，放完后一定存在对应序列合法）一共要插 个数，故 种。

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int P = 998244353;

int qpow(int a,int b){
    int res = 1;
    while(b){
        if(b&1) res = res*a%P;
        a = a*a % P;
        b >>= 1;
    }
    return res;
}

signed main(){
    int n;
    cin >> n;
    int res = 1;
    for(int i=1;i<=n;i++){
        res = res*i%P;
    }
    res = (qpow(2,n-1))*qpow(res,P-2)%P;
    cout << res;
}