2024/07/01
AtCoder Beginner Contest 360
E - Random Swaps of Balls
期望 \(dp\) 题
问题陈述
有 \(N - 1\) 个白球和一个黑球。这些 \(N\) 个球排成一排，黑球最初位于最左边的位置。
高桥正好要进行下面的操作 \(K\) 次。
- 在 \(1\) 和 \(N\) 之间均匀随机地选择一个整数，包括两次。设 \(a\) 和 \(b\) 为所选整数。如果是 \(a \neq b\) ，把左边的 \(a\) -th 和 \(b\) -th 两个球交换。
经过 \(K\) 次操作后，让黑球位于左边的 \(x\) -th 位置。求 \(x\) 的期望值，模为 \(998244353\) 。
模数 \(998244353\) 的期望值是多少？
可以证明所求的期望值总是有理数。此外，在本题的限制条件下，还可以证明如果用不可约分数 \(\frac{P}{Q}\) 表示这个值，那么就是 \(Q \not \equiv 0 \pmod{998244353}\) 。因此，存在一个唯一的整数 \(R\) ，使得 \(R \times Q \equiv P \pmod{998244353}, 0 \leq R \leq 998244353\) 。报告这个 \(R\) .
参考了 Lanly 的题解
首先，我们可以看到：对于每一个不为 \(1\) 位置，其价值相等
那么，我们自然设置出状态：
- 其在 \(1\) 号位上
- 其不在 \(1\) 号位上
对于第 \(i\) 次操作，位于 \(1\) 号位的期望为 \(dp_{i,0}\), 位于非 \(1\) 号位的期望为 \(dp_{i,1}\)
那么，黑球惨遭移动的概率为 $m = 2\frac{1}{n} \cdot \frac{n-1}{n} = \frac{2(n-1)}{n^2} $
故，黑球纹丝不动的概率为 \(s = 1 - m\)
黑球移动到某一个位置的概率为 \(to = \frac{move}{n - 1} = \frac{2}{n^2}\)
转移为：
\[dp_{i,0} = s \cdot dp_{i-1,0} + to \cdot dp_{i-1,1} \\ dp_{i,1} = m \cdot dp_{i-1,0} + (1 - to) \cdot dp_{i-1,1} \]最后，因为 \(p_1 = dp_{k,0} \ p_2 = p_3 = p_4 = ... = p_n = \frac{dp_{k,1}}{n-1}\)
由期望计算公式
\[E(X) = \sum_{i = 1}^n ip_i \]本题的答案
\[ans = \sum_{i = 1}^n ip_i = dp_{k,0} + \frac{dp_{k,1}}{n-1}\sum_{i = 2}^{n} i = dp_{k,0} + \frac{(n + 2)(n-1)}{2} \cdot \frac{dp_{k,1}}{n-1} = \frac{(n + 2)dp_{k,1}}{2} + dp_{k,0} \]AC-code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
const int mod = 998244353;
int qpow(int x,int k) {
int res = 1;
while(k) {
if(k & 1) res = (res * x) % mod;
x = (x * x) % mod;
k >>= 1;
}
return res;
}
int inv(int x) {
return qpow(x,mod - 2) % mod;
}
int dp[100005][2];
signed main() {
int n = rd(),k = rd();
if(n == 1) {
wt(1);
return 0;
}
dp[0][0] = 1;
int P = inv(n);
int P2 = (P * P) % mod;
int move = ((n-1)<<1) % mod * P2 % mod;
int stay = (1 - move + mod) % mod,to = (P2<<1) % mod;
for(int i = 1;i<=k;i++) {
dp[i][0] = (dp[i-1][0] * stay % mod + dp[i-1][1] * to % mod) % mod;
dp[i][1] = (dp[i-1][0] * move % mod + dp[i-1][1] * ((1- to + mod) % mod) %mod) % mod;
}
int ans = dp[k][0] + ((n + 2) * (n - 1) / 2) % mod * dp[k][1] % mod * inv(n-1) % mod;
wt(ans % mod);
return 0;
}