随机游走

这其实是一个题

给定$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$因为第一堆石头是需要被拿完的，后面算的是期望第二堆拿了多少，第三堆拿了多少。

然后就做完了。

cpp

#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;
}