题解：AT_abc360_e [ABC360E] Random Swaps of Balls

xiezheyuan · 2024-07-01 21:16:35 · 题解

简要题意

E - Random Swaps of Balls

有 n 个球，其中 n-1 球为白球，剩下一个球为黑球。初始时黑球为第 1 个球。

你可以进行 k 次操作，每次操作等概率随机选择两个整数 i,j\in[1, n]，然后交换第 i 个和第 j 个球。

求最终黑球位置期望，对 P=998244353 取模。
1\leq N<P,1\leq k\leq 10^5

思路

设 f_i 表示第 i 个操作后的答案，则有：

f_i=\begin{cases} 1&i=0\\ \frac{(n-1)(n-1)+1}{n^2}\cdot f_{i-1}+\frac{1}{n^2}\cdot \left(\frac{1}{2}n(n+1)-f_{i-1}\right)\cdot 2&\text{otherwise} \end{cases}

为什么呢？

对于第一部分 \frac{(n-1)(n-1)+1}{n^2} 表示有 (n-1)(n-1) 种情况没有选择黑球位置，还有 1 种情况 i,j 均是黑球位置，这些情况不会改变答案。
对于第二部分，则是选择了黑球位置。所有位置和显然可以用等差数列求和公式。但是需要注意可能选择黑球原有的位置，需要减去这一部分的贡献。然后选择的 i,j 有序，所以要乘上 2。

时间复杂度 O(k+\log n)。

代码

注意别溢出了。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 998244353;
int n, k, ans = 1;

int M(int x){
    return (x % mod + mod) % mod;
}

int fastpow(int a, int b){
    int ans = 1;
    while(b){
        if(b&1) ans = M(ans * a);
        a = M(a * a);
        b >>= 1;
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    int all = M(M(n * (n + 1)) * fastpow(2, mod - 2));
    int cb = fastpow(M(n * n), mod - 2);
    int nocb = M(M((n - 1) * (n - 1) + 1) * cb);
    for(int i=1;i<=k;i++) ans = M(M(nocb * ans) + M(cb * M((all - ans) * 2)));
    cout << ans << '\n';
    return 0;
}