I - Wish I Knew How to Sort
题意
每次随机选择下标 \(i, j\) 交换 \(a[i], a[j]\)，求变成不讲序列的期望次数。
思路
dp，同样也是期望 dp，先考虑暴力，可以状态压缩，那么 \(010\) 可以转移到:
\(100\)，\(010\)，\(001\)
这三种，然后我们发现，其实只有 \(001\) 有点用，而其他的就有点鸡肋，所以可以观察前两个串，会发现它们与目标串不同的地方有两个，所以它们与目标串的“距离”为 1，而第三个串的“距离”则为 0，那么就可以用这个“距离”作为代表这一类的标志、下标，我们发现这个“距离”最多也只有 \(\frac{n}{2}\) 所以可以用这个来做 dp，所以可以推出：\(dp_i = \frac{i^2}{\frac{n(n - 1)}{2}}dp_{i - 1} + \frac{\frac{n(n - 1)}{2}-i^2}{\frac{n(n - 1)}{2}}dp_i\)，这个时候我们发现式子里出现了类似 \(x=x\) 的东东，所以移项：
\(dp_i = \frac{i^2}{\frac{n(n - 1)}{2}}dp_{i - 1} + \frac{\frac{n(n - 1)}{2}-i^2}{\frac{n(n - 1)}{2}}dp_i\)
\(dp_i - \frac{\frac{n(n - 1)}{2}-i^2}{\frac{n(n - 1)}{2}}dp_i = \frac{i^2}{\frac{n(n - 1)}{2}}dp_{i - 1}\)
\((1 - \frac{\frac{n(n - 1)}{2}-i^2}{\frac{n(n - 1)}{2}})dp_i = \frac{i^2}{\frac{n(n - 1)}{2}}dp_{i - 1}\)
\(dp_i = \frac{\frac{i^2}{\frac{n(n - 1)}{2}}dp_{i - 1}}{(1 - \frac{\frac{n(n - 1)}{2}-i^2}{\frac{n(n - 1)}{2}})}\)
这个时候式子就没问题了，直接 dp 算即可
code
点击查看代码
#include <iostream>
#include <iomanip>
using namespace std;
using ll = long long;
const int MaxN = 200010, mod = 998244353;
ll a[MaxN], t, n, cnt, sum;
ll dp[MaxN];
ll qpow(ll a, ll b) {
ll res = 1;
for (ll i = 1; i <= b; i <<= 1) {
(b & i) && (res = res * a % mod);
a = a * a % mod;
}
return res;
}
int main() {
for (cin >> t; t; t--) {
cin >> n, cnt = sum = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i], sum += a[i] == 0;
}
for (ll i = 1; i <= n; i++) {
if (i <= sum) {
cnt += a[i] != 0;
} else if (i > sum) {
cnt += a[i] != 1;
}
}
cnt /= 2;
for (ll i = 1; i <= cnt; i++) {
ll a = n * (n - 1) % mod * qpow(2, mod - 2) % mod;
dp[i] = ((1 + dp[i - 1] * (i * i % mod * qpow(a, mod - 2) % mod) % mod) * qpow(((1 - ((a - i * i % mod) + mod) % mod * qpow(a, mod - 2) % mod) % mod + mod) % mod, mod - 2) % mod + mod) % mod;
}
cout << (dp[cnt] % mod + mod) % mod << endl;
}
return 0;
}