有 \(n\) 个种颜色的球，第 \(i\) 个颜色的球有 \(a_i\) 个。当袋子有至少两个不同颜色的球时，执行以下操作：
这些步骤均只需要 \(1s\)，输出无法操作的期望时间。
答案对 \(10^9+7\) 取模。
\(n\le 2500,a_i\le 10^5\)
算是比较 trickly 的时停技巧的使用了吧。
定义 \(S_t\) 表示时间 \(t\) 时的局面，定义 \(\phi(S_t)\) 表示时间 \(t\) 时的局面 \(S_t\) 的势函数，我们希望选择合适的势函数，使得 \(\phi(S_{end})\) 为一个常数，同时在期望意义下每次操作 \(\phi\) 均会减少 \(1\)，那么这样 \(\phi(S_{begin})-\phi(S_{end})\) 就是我们需要求的答案。
考虑定义 \(f(a_i)\) 表示颜色 \(i\) 有 \(a_i\) 个球的势函数，定义 \(F(S)=\sum f(a_i)\) 以表示局面的势函数，记 \(m=\sum a_i\)，那么有：
于是有：
由于我们希望 \(\phi(S_{t+1})-\phi(S_t)=-1\)，于是有：
由于我们希望的是更一般的情况，于是这个式子对于任意的 \(a_i\) 均成立，所以有：
恒成立。
故：
考虑定义 \(g(x)=f(x)-f(x-1)\)，那么 \(g(x+1)-g(x)=-\frac{m-1}{m-x}\)
接着我们认为 \(g(0)\) 和 \(f(0)\) 均为常数，那么有：
方便起见，规定 \(g(0)=m-1,f(0)=0\)，那么就有：
维护倒数和，递推至 \(\max a_i\) 即可。
此时，\(\phi(S_{end})=f(m)=0,\phi(S_{begin})=\sum f(a_i)\)
如果写线性逆元的话，复杂度为 \(\mathcal O(\max a+n)\)
\(Code:\)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < ‘0‘ || cc > ‘9‘ ) { if( cc == ‘-‘ ) flus = - flus ; cc = getchar() ; }
while( cc >= ‘0‘ && cc <= ‘9‘ ) cn = cn * 10 + cc - ‘0‘, cc = getchar() ;
return cn * flus ;
}
const int P = 1e9 + 7 ;
const int N = 1e5 + 5 ;
int fpow(int x, int k) {
int ans = 1, base = x ;
while(k) {
if(k & 1) ans = 1ll * ans * base % P ;
base = 1ll * base * base % P, k >>= 1 ;
} return ans ;
}
int n, m, c, a[N], f[N], inv[N] ;
signed main()
{
n = gi() ; f[0] = 0 ;
rep( i, 1, n ) a[i] = gi(), c += a[i], m = max( m, a[i] ) ;
rep( i, 0, m ) inv[i] = fpow(c - i, P - 2) ;
rep( i, 1, m ) inv[i] = (inv[i - 1] + inv[i]) % P ;
rep( i, 1, m ) f[i] = (c - 1) * (c - i) % P * inv[i - 1] % P ;
int ans = 0 ;
rep( i, 1, n ) ans = (ans + f[a[i]]) % P ;
cout << ans % P << endl ;
return 0 ;
}
原文：https://www.cnblogs.com/Soulist/p/13906776.html