好题!
考虑如何更简洁地描述 \(\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n [P_i > P_j] (j - i)\)。拆贡献,设 \(f_i = \sum\limits_{j = 1}^{i - 1} [P_j > P_i] - \sum\limits_{j = i + 1}^n [P_j < P_i]\),所求即为 \(\sum\limits_{i = 1}^n i \times f_i\)。注意到交换 \(i, i + 1\),\(f_i\) 无论如何都增加 \(1\),\(f_{i + 1}\) 无论如何都减少 \(1\)。并且 \(f_1 = 1 - P_1\)。可得 \(f_i = i - P_i\)。因此所求即为 \(\sum\limits_{i = 1}^n i \times (i - P_i) = \sum\limits_{i = 1}^n i^2 - \sum\limits_{i = 1}^n i \times P_i\)。
设 \(Q_{P_i} = i\),后面项可转化成 \(\sum\limits_{i = 1}^n i \times Q_i\)。不妨计数转期望,计算 \(\sum\limits_{i = 1}^n i \times E(Q_i)\)。注意到,如果 \(Q_i\) 至少被操作 \(1\) 次,那么最后到达 \(j\) 和 \(n - j + 1\) 的概率是相等的。因为位置 \(i\) 被换到位置 \(j\) 的方案数是 \(\min\{i, j, n - i + 1, n - j + 1\}\)。所以如果 \(Q_i\) 至少被操作了 \(1\) 次,\(E(Q_i) = \frac{n + 1}{2}\)。
剩下的部分是平凡的。算出 \(m\) 次操作均不包含 \(Q_i\) 的概率即可。
时间复杂度 \(O(n \log m)\),瓶颈在快速幂。
code
// Problem: E - Reverse and Inversion
// Contest: AtCoder - AtCoder Regular Contest 154
// URL: https://atcoder.jp/contests/arc154/tasks/arc154_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, a[maxn];
void solve() {
scanf("%lld%lld", &n, &m);
ll ans = 0;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
a[x] = i;
ans = (ans + 1LL * i * i % mod) % mod;
}
for (int i = 1; i <= n; ++i) {
ll p = ((n - a[i]) * (n - a[i] + 1) / 2 + (a[i] - 1) * a[i] / 2) % mod * qpow(n * (n + 1) / 2 % mod, mod - 2) % mod;
ans = (ans - (qpow(p, m) * a[i] % mod + (1 - qpow(p, m) + mod) % mod * (n + 1) % mod * inv2 % mod) % mod * i % mod + mod) % mod;
}
ans = ans * qpow(n * (n + 1) / 2 % mod, m) % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Inversion AtCoder Regular Contest Reverseinversion atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest