[ARC228C] Partially Sort

· · 题解

或许更好的阅读体验。

思路：

显然拆贡献去做，考虑一对原来逆序对的贡献 (i, j)，即 i < j, p_i > p_j，如果操作不涉及到它们，那么依旧是逆序对，方案数是 2^{n - 2}；否则如果两个都涉及到，那么它们肯定不会造成贡献（因为排序了），否则只会涉及到一个。

设没有被选的那个是 x，考虑它的贡献，你发现对于排序后的那些数，要么都在左边构成逆序对，要么都在右边构成逆序对，这是显然的；具体的，考虑选的 i < x 的数量 a 和 p_i < p_x 的数量 b，如果 b < a，说明贡献在左边构成逆序对，数量是 a - b；否则在右边构成逆序对，贡献是 b - a。

所以对于 x，只要求出选的 i < x 的数量 a 和 p_i < p_x 的数量 b，那么贡献是 |a - b|；先算出全局 p_i < p_x 的数量 y = p_x - 1，和 x 前面 <p_x 的数量 z，枚举一下 c 表示前面选的 <p_x 的个数：

\sum_{a \le x - 1} \sum_{b \le y} |a - b|\sum_{c \le z} \binom{z}{c} \binom{y - z}{b - c} \binom{x - 1 - z}{a - c} 2^{n - x - (y - z)}

于是问题变为快速算：

\sum_{a \le x - 1} \sum_{b \le y} |a - b|\sum_{c \le z} \binom{z}{c} \binom{y - z}{b - c} \binom{x - 1 - z}{a - c}

考虑换元 i = a - c, j = b - c 分别表示选的 < x 中 > p_x 的数量和 >x 中 <p_x 的数量，那么式子变为：

\sum_{i \le x - 1 - z} \sum_{j \le y - z} |i - j| \binom{x - 1 - z}{i} \binom{y - z}{j} \sum_{c \le z} \binom{z}{c}

那么 c 就是独立的了，系数是 2^z，令 n = x - 1 - z, m = y - z，对于单个 x 转化为求：

\begin{aligned} Ans &= \sum_{i \le n} \sum_{j \le m} |i - j| \binom{n}{i} \binom{m}{j} \\ &= \sum_{i \le n} \sum_{j \le i} (i - j) \binom{n}{i} \binom{m}{j} + \sum_{j \le m} \sum_{i \le j} (j - i) \binom{n}{i} \binom{m}{j} \\ &= f(n, m) + f(m, n)\end{aligned}

然后考虑：

\begin{aligned} f(n, m) &= \sum_{i \le n} \sum_{j \le i} (i - j) \binom{n}{i} \binom{m}{j} \\ &= n \sum_{i \le n} \binom{n - 1}{i - 1} \sum_{j \le i} \binom{m}{j} \\ &- m \sum_{i \le n} \binom{n}{i} \sum_{j \le i} \binom{m - 1}{j - 1} \\ &= n \sum_{i \le n - 1} \binom{n - 1}{i - 1} \sum_{j \le i + 1} \binom{m}{j} \\ &- m \sum_{i \le n} \binom{n}{i} \sum_{j \le i - 1} \binom{m - 1}{j}\end{aligned}

现在你发现难点在于 \sum_{i \le x'} \binom{x'}{i} \sum_{j \le i} \binom{y'}{j} 这种类型式子上，先反转下标转化成 i + j 的限制，考虑枚举 k = i + j，然后范德蒙雷卷积，那么：

\begin{aligned} LHS &= \sum_{i \le x'} \binom{x'}{i} \sum_{j \le i} \binom{y'}{j} \\ &= \sum_{i \le x'} \binom{x'}{i}\sum_{y'\le i +j} \binom{y'}{y' - j} \\ &=\sum_{k \ge y'} \sum_i \binom{x'}{i} \binom{y'}{k - i} \\ &= \sum_{k \ge y'} \binom{x' + y'}{k} \end{aligned}

这个 trick 和 [ARC230A] Meeting on Tree 完全一致，不知道为什么这么近的时间出同一个何意味？？？而且一个 900，一个 3000！！！

于是：

f(n, m) = n \sum_{k \ge m - 1} \binom{n + m - 1}{k} - m \sum_{k \ge m} \binom{n + m - 1}{k}

你发现这是一个组合数后缀和的问题，可以写成前缀和的形式好看点：

f(n, m) = (n - m) \sum_{k = 0}^{n - 1} \binom{n + m - 1}{k} + n \binom{n + m - 1}{n}

上指标每次询问都不固定，于是直接暴力莫队去维护即可。

时间复杂度为 O(n \sqrt n)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 4e5 + 10, mod = 998244353, inv2 = (mod + 1) >> 1;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
} 
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int add(int x, int y){
    return (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void getdec(int &x, int y){
    x = (x < y) ? (x - y + mod) : (x - y);
}
inline int dec(int x, int y){
    return (x < y) ? (x - y + mod) : (x - y);
}
inline int qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int n, ans, t, cnt, now;
int siz[N], fac[N], ifac[N], p2[N], p[N], a[N], A[N];
int pz[N], Ans[N];
struct Ques{
    int l, r, w, id;
    inline bool operator<(const Ques&rhs)const{
        if(A[l] ^ A[rhs.l])
          return A[l] < A[rhs.l];
        return r < rhs.r;
    }
}Q[N];
inline void upd(int x, int v){
    for(int i = x; i <= n; i += lowbit(i))
      a[i] += v;
}
inline int ask(int x){
    int sum = 0;
    for(int i = x; i; i -= lowbit(i))
      sum += a[i];
    return sum;
}
inline void init(){
    fac[0] = fac[1] = p2[0] = 1, p2[1] = 2;
    for(int i = 2; i < N; ++i){
        fac[i] = 1ll * fac[i - 1] * i % mod;
        p2[i] = 2ll * p2[i - 1] % mod;
    }
    ifac[N - 1] = qpow(fac[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; --i)
      ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod;
}
inline int binom(int n, int m){
    if(m > n || m < 0 || n < 0)
      return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
// inline int f(int n, int m){
//     int s = 0, sum = 0;
//     for(int k = 0; k <= n - 1; ++k)
//       getadd(s, binom(n + m - 1, k));
//     getdec(sum, 1ll * s * m % mod);
//     getadd(s, binom(n + m - 1, n));
//     getadd(sum, 1ll * s * n % mod);
//     return sum;
// }
// inline int solve(int n, int m){
//     return f(n, m) + f(m, n);
// }
inline void getqry(int n, int m, int id){
    getadd(Ans[id], 1ll * n * binom(n + m - 1, n) % mod);
    Q[++cnt] = {n + m - 1, n - 1, dec(n, m), id};
}
inline void getques(int n, int m, int id){
    getqry(n, m, id);
    getqry(m, n, id);
}
int main(){
    init();
    n = read();
    for(int x = 1; x <= n; ++x){
        p[x] = read();
        int y = p[x] - 1, z = ask(p[x]);
        pz[x] = z;
        getques(x - 1 - z, y - z, x);
        getadd(ans, 1ll * (x - 1 - z) * p2[n - 2] % mod);
        // cerr << x << ' ' << y << ' ' << z << '\n';
        // for(int a = 0; a < x; ++a)
        //   for(int b = 0; b <= y; ++b)
        //     for(int c = 0; c <= b; ++c)
        //       getadd(ans, 1ll * binom(z, c) * binom(y - z, b - c) % mod * binom(x - 1 - z, a - c) % mod % mod * abs(a - b) % mod);
        upd(p[x], 1);
    }
    t = n / sqrt(cnt) + 1;
    for(int i = 1; i <= n; ++i)
      A[i] = (i - 1) / t + 1;
    sort(Q + 1, Q + cnt + 1);
    int l = 1, r = 1;
    now = 2;
    for(int i = 1; i <= cnt; ++i){
        while(l < Q[i].l){
            now = dec(2ll * now % mod, binom(l, r));
            l++;
        }
        while(r > Q[i].r){
            now = dec(now, binom(l, r));
            r--;
        }
        while(l > Q[i].l){
            --l;
            now = 1ll * add(now, binom(l, r)) * inv2 % mod;
        }
        while(r < Q[i].r){
            ++r;
            now = add(now, binom(l, r));
        }
        getadd(Ans[Q[i].id], 1ll * now * Q[i].w % mod);
    }
    for(int x = 1; x <= n; ++x){
        int y = p[x] - 1, z = pz[x];
        getadd(ans, 1ll * p2[n - x - (y - z) + z] * Ans[x] % mod);
    }
    write(ans);
    return 0;
}