给个高中做法

考虑到第 kk 次黑球的位置只与第 $ k-1$ 次的位置有关，不妨将球现在的位置设为 ii ，那么随机选择一次后仍在 $ i$ 的概率为 1n2\frac{1}{n^2} + (n−1)2n2\frac{(n-1)^2}{n^2},位于j(j≠i)j(j\not=i)的概率为2n2\frac{2}{n^2} 。（把a=ba=b的情况考虑在内，即球的位置不变动，对概率无影响。）

仿照2023年新高考一卷次压轴题，我们设 pkp_k 表示传k次后黑球出现在1号位置的概率，那么我们有pk=[1n2p_k=[\frac{1}{n^2} + (n−1)2n2)]⋅pk−1+2n2⋅(1−pk−1)\frac{(n-1)^2}{n^2})]\cdot p_{k-1}+ \frac{2}{n^2} \cdot (1-p_{k-1})

化简得 $(p_k-\frac{1}{n}) = \frac{n2-2n}{n2}\cdot(p_{k-1}- \frac{1}{n} $ )

化简得 pk=1n+n−1n⋅(n2−2nn2)k−1p_k = \frac1n+\frac{n-1}{n}\cdot(\frac{n^2-2n}{n^2})^{k-1}

再考虑又 $ k-1$ 次到第 kk 次 ，不妨设第 k−1k-1 次位于 ii ，当 i=1i=1 时，贡献为 n2−2n+2n2+2n2∑j=2nj\frac{n^2-2n+2}{n^2}+\frac2{n^2}\sum_{j=2}^{n}j

当 i≠1i\not =1时，贡献为 ∑i=2n[(n2−2n+2n2)i+∑j=1,j≠in(2n2)j]\sum_{i=2}^{n}[(\frac{n^2-2n+2}{n^2})i+\sum_{j=1,j\not=i}^{n}(\frac{2}{n^2})j]

进而答案就是 pk−1(n2−2n+2n2+2n2∑j=2nj)+(1−pk−1n−1)p_{k-1}(\frac{n^2-2n+2}{n^2}+\frac2{n^2}\sum_{j=2}^{n}j)+(\frac{1-p_{k-1}}{n-1}) $\sum_{i=2}{n}[(\frac{n2-2n+2}{n^2}) \cdot i+\frac{2}{n2}\sum_{j=1,j!=i}{n} j] = $

2n−1n⋅pk−1+n2+2n−22n⋅(1−pk−1)\frac{2n-1}{n}\cdot p_{k-1}+\frac{n^2+2n-2}{2n}\cdot(1-p_{k-1})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<ctime>
#define ll long long
using namespace std;
const ll mod= 998244353;
const int maxn=1e5+50;
ll fp (ll x,ll y){
	if(y==0)return 1LL;
	if(y==1)return x;
	ll ans=fp(x,y/2)%mod;
	if(y%2)return (x*ans%mod)*ans%mod;
	else return ans*ans%mod;
}

ll p[maxn];
ll n,k;
int main() {
	cin>>n>>k;
    p[k-1]=(fp(n,mod-2)%mod+((n-1)*fp((n-2)*n%mod,k-1)%mod)*fp(fp(n,2*k-2)%mod,mod-2)%mod*fp(n,mod-2)%mod)%mod;
	ll ans=(((n+2)*n%mod-2)%mod)*(1+mod-p[k-1])%mod*fp(2*n,mod-2)%mod+(2*n-1)*p[k-1]%mod*fp(n,mod-2)%mod;
	cout<<ans%mod<<endl;
	return 0;
}