CF850F Rainbow Balls [* interesting]
有 (n) 个种颜色的球，第 (i) 个颜色的球有 (a_i) 个。当袋子有至少两个不同颜色的球时，执行以下操作：
- 先后随机取出两个球，然后将第二个球涂成第一个球的颜色。（允许同色）
这些步骤均只需要 (1s)，输出无法操作的期望时间。
答案对 (10^9+7) 取模。
(nle 2500,a_ile 10^5)
Solution
算是比较 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)，那么有：
- 我们有 (frac{a_i(a_i-1)}{m(m-1)}) 的概率选中两个 (i) 类球
- 我们有 (frac{a_ia_j}{m(m-1)}) 的概率将 (i) 变成 (j)
于是有：
[egin{aligned}
&phi(S_{t+1})=frac{1}{m(m-1)}igg(sum_i a_i(a_i-1)phi(S_t)+sum_isum_{j
e i} a_ia_j(phi(S_t)+f(a_i+1)-f(a_i)+f(a_j-1)-f(a_j))igg)
\&=frac{1}{m(m-1)}igg(sum_i Big(a_i(a_i-1)+a_i(m-a_i)Big)phi(S_t)+sum_i a_i(m-a_i)(f(a_i+1)-2f(a_i)+f(a_i-1))igg)
\&=frac{1}{m(m-1)}igg(sum_i Big( ma_i-a_iBig)phi(S_t)+sum_i a_i(m-a_i)(f(a_i+1)-2f(a_i)+f(a_i-1))igg)
\&=frac{1}{m(m-1)}igg(m(m-1)phi(S_t)+sum_i a_i(m-a_i)(f(a_i+1)-2f(a_i)+f(a_i-1))igg)
\&=phi(S_t)+frac{1}{m(m-1)}sum_i a_i(m-a_i)(f(a_i+1)-2f(a_i)+f(a_i-1))
end{aligned}]
由于我们希望 (phi(S_{t+1})-phi(S_t)=-1)，于是有：
[egin{aligned}
&-1=frac{1}{m(m-1)}sum_i a_i(m-a_i)(f(a_i+1)-2f(a_i)+f(a_i-1))
\&0=~m+frac{1}{m-1}sum_i a_i(m-a_i)(f(a_i+1)-2f(a_i)+f(a_i-1))
\&0=sum_i a_iigg(1+frac{m-a_i}{m-1}(f(a_i+1)-2f(a_i)+f(a_i-1))igg)
end{aligned}]
由于我们希望的是更一般的情况，于是这个式子对于任意的 (a_i) 均成立，所以有：
[1+frac{m-x}{m-1}(f(x+1)+f(x-1)-2f(x))=0
]
恒成立。
故：
[(f(x+1)+f(x-1)-2f(x))=-frac{m-1}{m-x}
]
考虑定义 (g(x)=f(x)-f(x-1))，那么 (g(x+1)-g(x)=-frac{m-1}{m-x})
接着我们认为 (g(0)) 和 (f(0)) 均为常数，那么有：
[g(x)=g(0)+sum_{j=0}^{x-1} frac{1-m}{m-j}
]
[egin{aligned}
&f(x)=f(0)+sum_{j=1}^{x} g(j)
\&=f(0)+xcdot g(0)-sum_{j=0}^{x-1}frac{(m-1)(x-j)}{m-j}
\&=f(0)+xcdot g(0)-x(m-1)+sum_{j=0}^{x-1}frac{(m-1)(m-j-x+j)}{m-j}
\&=f(0)+xcdot g(0)-x(m-1)+(m-1)(m-x)sum_{j=0}^{x-1}frac{1}{m-j}
end{aligned}]
方便起见，规定 (g(0)=m-1,f(0)=0)，那么就有：
[f(m)=0
]
[f(x)=(m-1)(m-x)sum_{j=0}^{x-1}frac{1}{m-j}
]
维护倒数和，递推至 (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 ;
}