随机游走

会被加入即将出现被鸽的概率与期望专题。

这其实是一个题

给定 $ n $ 堆石头每一堆有 $ a_i $ 个，每次随机选择仍然有石头的一堆并且从里面拿出一个石头。求期望多少次后第一堆石头不再有石头。

第一步是一个结论，原题等价于随机选择一堆石头，如果这堆石头已经没有石头了就重新随机，直到有石头为止。其实这个结论无论是否带权都成立，可以记住。

我们可以对出了第一堆石头外的石头堆分开考虑。假设 $ E(i) $ 表示第1堆石头被拿完的时候第 $ i $ 堆期望被拿了多少个。一下直接讨论第二堆的情况，其他情况同理。

然后我们可以看成是在生成一个序列，每次有 $ frac{1}{n} $ 概率生成一个 1 ，代表从第一堆石头拿了一个石头走，如果没有石头就无视，同时又 $ frac{1}{n} $ 概率生成一个 2 ，代表从第二堆石头拿了一个石头走，同样如果没有石头就无视，然后有 $ frac{n-2}{n} $ 概率生成一个 3 ，代表从其他石头拿。

而 $ E(2) $ 其实就是在生成第 $ A[1] $ 个 1 时已经生成的2的期望个数。根据期望的定义，我们假设 $ A[1] $ 个 1 出现前有 $ k $ 个2的概率为 $ P(k) $ 那么 $ E(2) = sum P(k) $。

接下来的问题就是怎么去计算 $ P(k) $ 了，$ P(k) $ 的计算可以考虑枚举第 $ A[1] $ 个 1 出现前出现了多少个3，那么

$P(k) = displaystyle (frac{1}{n})sum_{i geq 0} frac{(i+A_1-1+k)!}{i!(A_1-1)!k!}(frac{1}{n})^{A_1+k-1} (frac{n-2}{n})^i $

为啥是 $ A_1 - 1 $ 呢，因为第 $ A_1 + k + i $ 个位置已经被钦定了1了，而钦定这个位置是 1 的概率就在于前面的 $ frac{1}{n} $

考虑化简这个式子，最后化简出来是这个东西：

$ P(k) = displaystyle ( frac{1}{n} )^{A_1+k} frac{(A_1+k-1)!}{(A_1-1)!k!} ( frac{1}{1-p} )^{A_1+k} $

这个东西可以计算前缀和以及 (kP(k)) 的前缀和。注意，在计算 (A_j) 的时候其实算的是 $ kP(k) $ 前缀和在 $ A_j $ 前的项，而后面的项 都应当乘上 (A_j) 。因为你考虑多拿了的话由于前面的结论，相当于无视这一步，我们仍然拿了 $ A_j $ 个石头。这个概率一直加到正无穷和是1，所以只需要用 1 减去个前缀和就好了。

注意答案要加上 $ A_1 $ 因为第一堆石头是需要被拿完的，后面算的是期望第二堆拿了多少，第三堆拿了多少。

然后就做完了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 1000006
#define int long long
#define P 323232323
int power( int x , int a ) {
	int ans = 1 , cur = x % P;
	while( a ) {
		if( a & 1 ) ans *= cur , ans %= P;
		cur *= cur , cur %= P , a >>= 1;
	}
	return ans;
}
int n;
int A[MAXN];
int J[MAXN] , S[MAXN] , Sk[MAXN];
signed main() {
	cin >> n;
	for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&A[i]);
	if( A[1] == 0 ) return puts("0") ,0;
	J[0] = 1; for( int i = 1 ; i < MAXN ; ++ i ) J[i] = J[i - 1] * i % P;
	int p = ( 2 ) * power( n , P - 2 ) % P , a = A[1] - 1;
	S[0] = power( power( p * n % P , A[1] ) , P - 2 );
	for( int k = 1 ; k < 500006 ; ++ k ) {
		int pp = J[a + k] * power( J[a] * J[k] % P * power( p * n % P , a + k + 1 ) % P , P - 2 ) % P;
		S[k] = ( S[k - 1] + pp ) % P , Sk[k] = ( Sk[k - 1] + k * pp % P ) % P;
	}
	int res = 0;
	for( int i = 2 ; i <= n ; ++ i ) 
		res += ( Sk[A[i]] + ( 1 - S[A[i]] + P ) % P * A[i] % P ) % P , res %= P;
	cout << ( res + A[1] ) % P << endl;
}