题解：P14639 【OIMO Round 1】世界线

· · 题解

首先我们将作为前缀最大值的取出来，作为前缀最小值的取出来，如果都可以的，先不考虑。

则我们取出来的是一个单调不降序列和一个单调不升序列，将其中一个序列插入另一个序列中，方案数容易算出（经典 n 个相同的球放入 m 个不同可空盒子中的方案数）。

接着考虑都可以的数，这些数一定是一个前缀，有两个思路，第一种都可以的数有个性质，它们都是跟第一个数相同的数，且它们被限制一定要进入的某个序列一定都相同，所以枚举这个即可，最终容斥掉都可以的，都可以的一定是全部跟第一个相同的数都放在前面。这个是官解思路。

另一个思路是我的思路，枚举有多少个跟第一个数相同的数一定放入第一个序列，如果数量非零，那么它们一定要放入第一个比第一个数大的数的后面。数这个东西就好了。

:::info[code]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using lll = __int128;
using ulll = unsigned __int128;

#define int ll

#ifndef ONLINE_JUDGE
template <typename T>
void _debug(const T &t) { cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T &t, const Args &...rest)
{
    cerr << t << ' ';
    _debug(rest...);
}
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)
#else
#define debug(...) 0
#endif
template <typename Iterator>
struct _Range
{
    Iterator l, r;
    friend ostream &operator<<(ostream &os, const _Range &t)
    {
        if (t.l >= t.r)
        {
            return os << "[]";
        }
        os << '[' << *t.l;
        for (auto i = next(t.l); i != t.r; ++i)
        {
            os << ',' << *i;
        }
        return os << ']';
    }
};
template <typename Container>
auto Range(const Container &c) -> _Range<decltype(begin(c))> { return {begin(c), end(c)}; }
template <typename T, size_t N>
auto Range(const T (&arr)[N]) -> _Range<const T *> { return {arr, arr + N}; }
template <typename Container>
auto Range(const Container &c, size_t l, size_t r) -> _Range<decltype(begin(c))>
{
    auto start = begin(c) + min(l, c.size());
    auto end = begin(c) + min(r, c.size());
    return {start, end};
}
template <typename T, size_t N>
auto Range(const T (&arr)[N], size_t l, size_t r) -> _Range<const T *> { return {arr + min(l, N), arr + min(r, N)}; }
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << '(' << p.first << ',' << p.second << ')'; }
#define D debug
#define Rg Range
#define ifD(cond, ...)      \
    if (cond)               \
    {                       \
        debug(__VA_ARGS__); \
    }
#undef int

const int N = 1e6 + 5, mod = 998244353;
int n, a[N];
ll res, fac[N], inv[N];

ll qpow(ll x, int k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * x % mod;
        x = x * x % mod, k >>= 1;
    }
    return res;
}

ll C(int n, int m) {
    return n >= m ? fac[n] * inv[m] % mod * inv[n - m] % mod : 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for (int i = n; i; --i) inv[i - 1] = inv[i] * i % mod;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1, j = i; i <= n; ++i) {
        // 有 n-j 个盒子，有 i-1 个球
        j = i;
        while (a[j + 1] == a[i]) ++j;
        if (a[i] == a[i - 1]) res += C(i - 1 + n - j - 1, n - j - 1);
        else res += C(n - 1, n - i);
    }
    cout << res % mod;
    return 0;
}

:::