解析

二倍相鄰項，就要想裂項

純數學題
一道黑色的小凱的疑惑

設總球數為 $s$
我們先欽定一種顏色留到最后，那么其他顏色可以等價考慮
設 $f_i$ 為欽定的顏色的球有 $i$ 個，涂完需要的期望次數
則有：
$$f_i=(f_{i?1}+f_{i+1})\times p+f_i\times (1?2p)+w_i$$
其中 $p$ 表示有序取出兩個不同色球的概率，$w_i$ 表示有 $i$ 個球的顏色留到最后的概率。
不難發現 $p=\frac{i(s?i)}{s(s?1)}$，考慮如何求 $w_i$。
首先有： $$w_0=0,w_s=1$$。
和 $f$ 的轉移類似的，有：$$w_i=(w_{i?1}+w_{i+1})\times p+w_i\times (1?2p)$$
化簡移項，得：
$$w_{i+1}?w_i=w_i?w_{i?1}$$
也就是說 $w$ 是一個等差數列，那么顯然就有：
$$w_i=\frac{i}{s}$$
把 $p,w$ 帶回原來的轉移式：
$$f_i=(f_{i?1}+f_{i+1})\times \frac{i(s?i)}{s(s?1)}+f_i\times (1?\frac{2i(s?i)}{s(s?1)})+\frac{i}{s}$$
化簡，得：
$$2f_i=f_{i+1}+f_{i?1}+\frac{s?1}{s?i}$$
也就是：
$$f_i?f_{i+1}=f_{i?1}+f_i+\frac{s?1}{s?i}$$
把 $i=1$ 帶入，有：
$$f_2=2f_1+1$$
又有：
$$f_1=f_1?f_s=\sum _{i=2}^s(f_{i?1}?f_i)=(s?1)(f_1?f_2)+\sum _{i=2}^{s?1}\frac{s?1}{s?i}\times (s?i)$$
后面那個和式是由于對于一個 $\frac{s?1}{s?i}$，它會產生 $s?i$ 次貢獻。
把 $f_2=2f_1+1$ 帶入，得到：
$$f_1=\frac{(s?1{)}^2}{s}$$
得到 $f_1$ 之后，后面順推即可。
過程中快速冪求逆元，時間復雜度 $O(n\log \mathrm{m}\mathrm{o}\mathrm{d})$。

代碼

（式子推完代碼幾乎沒有任何難度了…）

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; } ll a[N]; ll s,f[N],mx;signed main() { #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifn=read();for(int i=1;i<=n;i++) a[i]=read(),s+=a[i],mx=max(mx,a[i]);f[1]=(s-1)*(s-1)%mod*ksm(s,mod-2)%mod;f[2]=(2*f[1]-1+mod)%mod;for(int i=2;i<mx;i++) f[i+1]=(2*f[i]-f[i-1]+mod-(s-1)*ksm(s-i,mod-2)%mod+mod)%mod;ll ans(0);for(int i=1;i<=n;i++) (ans+=f[a[i]])%=mod;printf("%lld\n",ans);return 0; } /* */

總結

以上是生活随笔為你收集整理的CF850F Rainbow Balls（数学、期望）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。