「题解」ARC154E Reverse and Inversion

AtomAlpaca

题意
题解
代码

题意

给定 $n,m$ 两个正整数和一个 $n$ 的排列 $P$ 。重复进行如下操作 $m$ 次：

- 选定 $1\le i\le j\le n$ ，并将 $P_i,P_{i+1},..,P_j$ 翻转。

对于所有 $(\frac{n(n+1)}{2})^m$ 种方案，计算 $\sum_{i<j}[P_i>P_j](j-i)$ 的值的和。

集训讲题推荐题目，感觉很厉害。

题解

首先对所有方案统计有点吓人，我们不妨先假设已知最后的 $P$ 从 $\sum_{i<j}[P_i>P_j](j-i)$ 这个式子入手。

首先我们考虑对于每个位置 $i$ 计算它的贡献。那么有： $ans_i = i(\sum_{j=1}^{i-1}{[P_j > P_i]} - \sum_{j = i + 1}^{n}{[P_j < P_i]})$

然后我们考虑这样两个式子：

$\begin{aligned} \sum_{j=1}^{i - 1}{[P_j > P_i]} + \sum_{j = i + 1}^{n}{[P_j > P_i]} &= n - P_i \\ \sum_{j=i+1}^{n}{[P_j < P_i]} + \sum_{j=i+1}^{n}{[P_j > P_i]} &= n - i \end{aligned}$

两式相减恰好是上述式子的右侧，也就是得到 $ans_i=i^2 - iP_i$ ，故 $ans = \sum_{i=1}^{n}{i^2} - \sum_{i=1}^{n}{iP_i}$ 。

我们不妨求上述式子的期望。首先可以先把 $i^2$ 分离出来，只处理后面。求某个位置的期望值比较困难，我们不妨求 $P_i$ 最后所在位置的期望。

对于 $i < j$ ，一次操作后 $i$ 到达 $j$ 的方案数是 $\min(i, n - j + 1)$ 。比较直观地证一下：

$1 \dots i \dots \frac{i+j}{2} \dots j \dots n$

我们考虑从对称中心往两边拓展，那么得到的有效区间个数就是 $i, j$ 分别到两边到距离到最小值。

那么我们考虑把它写成 $\min(i, j, n - i + 1, n - j + 1)$ 的形式，就把它推广到了 $i > j$ 的情况。这时我们发现，把 $i$ 换到 $j$ 和换到和它对称的 $n - j + 1$ 的方案是一样到，因此我们得到 $i$ 经过交换后到位置期望是 $\dfrac{n+1}{2}$ ，也就是序列的中心。

考虑 $i$ 被交换走的概率，应该是 $\left(1 - \dfrac{\binom{i}{2}+\binom{n-i+2}{2}}{\binom{n+1}{2}}\right)^m$ 。我们令其为 $K$ 。则 $i$ 位置的期望就是 $K\dfrac{n+1}{2}+(1-K)i$ 。因此答案为 $ans = \sum_{i=1}^{n}{i^2} - P_i\sum_{i=1}^{n}{K\dfrac{n+1}{2}+(1-K)i}$ 。直接求解即可，复杂度 $O(n\log n)$ ，瓶颈在求逆元。

代码

#include <bits/stdc++.h> 

typedef long long ll;
const int MOD = 998244353;
const int MAX = 2e5 + 5;

ll n, m, ans;
ll p[MAX], frc[MAX], ifrc[MAX], inv[MAX];

ll qp(ll a, ll x) { ll res = 1; for (; x; a = a * a % MOD, x >>= 1) { if (x & 1) { res = res * a % MOD; } } return res; }
ll C(ll x, ll y) { return frc[x] * ifrc[y] % MOD * ifrc[x - y] % MOD; }
void init(int x)
{
    frc[0] = ifrc[0] = inv[0] = 1;
    for (int i = 1; i <= x; ++i) { frc[i] = frc[i - 1] * i % MOD; } ifrc[x] = qp(frc[x], MOD - 2);
    for (int i = x - 1; i >= 1; --i) { ifrc[i] = ifrc[i + 1] * (i + 1) % MOD; }
    for (int i = 1; i <= x; ++i) { inv[i] = ifrc[i] * frc[i - 1]; }
}

int main()
{
    scanf("%lld%lld", &n, &m); init(MAX - 3);
    for (int i = 1; i <= n; ++i) { scanf("%lld", &p[i]); }
    for (int i = 1; i <= n; ++i)
    {
        ll P = qp((C(n - i + 1, 2) + C(i, 2)) % MOD * qp(C(n + 1, 2), MOD - 2) % MOD, m);
        ll q = (1ll * i * P % MOD + (n + 1) * inv[2] % MOD * (1 - P + MOD) % MOD) % MOD;
        ans = (ans + 1ll * i * i % MOD - q * p[i] % MOD + MOD) % MOD;
        //  printf("%lld", ans);
    }
    printf("%lld", ans * qp(C(n + 1, 2), m) % MOD);
}

Table of contents

题意

题解

代码