題目鏈接

題目描述

給定 $n$ 種顏色的球，每種球有 $a_i$ 個，對這些球執行以下操作：

• 有順序地任意取兩個球，將第二個球涂上第一個球的顏色，重復該操作至所有球顏色相同。

求期望操作次數，對 $10^9+7$ 取模。
數據范圍：$n\le 2500$，$1\le a_i\le 10^5$。

Solution

• 設 $f_i$ 表示當前有 $i$ 個球，將所有球變為該顏色的期望次數，$s$ 表示球的總數，$p$ 表示當前取出的兩個球第一個與最終顏色相同，第二個與最終顏色不同的概率。
  根據題意，有 $$p=\frac{i\times (s?i)}{s\times (s?1)}$$$$f_i=p\times f_{i?1}+p\times f_{i+1}+(1?2p)\times f_i+v$$其中 $v$ 為這一步操作對最終答案的貢獻，也就是該顏色成為最終顏色的概率。
• 設 $g_i$ 表示當前顏色成為最終顏色的概率，有 $g_0=0$，$g_1=1$，且 $g_i=p\times g_{i?1}+p\times g_{i+1}+(1?2p)\times g_i$。
  轉化可得 $g_i?g_{i?1}=g_{i+1}?g_i$，等差數列求和可得 $g_i=\frac{i}{s}$，即 $v=\frac{i}{s}$。
• 那么現在有$$f_i=p\times f_{i?1}+p\times f_{i+1}+(1?2p)\times f_i+\frac{i}{s}$$轉化后有$$f_i?f_{i+1}=f_{i?1}?f_i+\frac{s?1}{s?i}$$
• 考慮求 $f_1$ 和 $f_2$ 后線性遞推，由于 $f_0$ 不存在，代入后有 $f_2=2f_1?1$。
  $$\begin{array}{rl}{f}_1& =f_1?f_s\\ & =\sum _{i=2}^s{f}_{i?1}?f_i\\ & =(s?1)\times (f_1?f_2)+\sum _{i=2}^{s?1}\frac{s?1}{s?i}\times (s?i)\\ & =(s?1)\times (1?f_1)+(s?1)\times (s?2)\end{array}$$
• 所以$$f_1=\frac{(s?1{)}^2}{s}$$線性遞推即可求解，答案為 ${\sum }_{i=1}^n{f}_{a_i}$。

Code

#include<cstdio> using namespace std; const int maxn=100010,MLY=1000000007; int f[maxn],n,a[maxn],s,ans; inline int power(int a,int b){int ans=1;while(b){if(b&1)ans=1ll*ans*a%MLY;a=1ll*a*a%MLY;b>>=1;}return ans; } int main(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]),s+=a[i];f[1]=(s-1ll)*(s-1)%MLY*power(s,MLY-2)%MLY;f[2]=(2ll*f[1]-1+MLY)%MLY;for(int i=2;i<100000;++i)f[i+1]=((2ll*f[i]-f[i-1]-(s-1ll)*power(s-i,MLY-2))%MLY+MLY)%MLY;for(int i=1;i<=n;++i)ans=(ans+f[a[i]])%MLY;printf("%d",ans);return 0; }

總結

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

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