莒县网站制作,wordpress忘记密码如何重新安装,兰州设计公司有哪些,网络营销工程师培训题目链接 题目描述
给定 nnn 种颜色的球#xff0c;每种球有 aia_iai 个#xff0c;对这些球执行以下操作#xff1a;
有顺序地任意取两个球#xff0c;将第二个球涂上第一个球的颜色#xff0c;重复该操作至所有球颜色相同。
求期望操作次数#xff0c;对 109710^9… 题目链接 题目描述
给定 nnn 种颜色的球每种球有 aia_iai 个对这些球执行以下操作
有顺序地任意取两个球将第二个球涂上第一个球的颜色重复该操作至所有球颜色相同。
求期望操作次数对 109710^971097 取模。 数据范围n≤2500n\le 2500n≤25001≤ai≤1051\le a_i\le 10^51≤ai≤105。
Solution
设 fif_ifi 表示当前有 iii 个球将所有球变为该颜色的期望次数sss 表示球的总数ppp 表示当前取出的两个球第一个与最终颜色相同第二个与最终颜色不同的概率。 根据题意有 pi×(s−i)s×(s−1)p\frac{i\times(s-i)}{s\times(s-1)}ps×(s−1)i×(s−i)fip×fi−1p×fi1(1−2p)×fivf_ip\times f_{i-1}p\times f_{i1}(1-2p)\times f_ivfip×fi−1p×fi1(1−2p)×fiv其中 vvv 为这一步操作对最终答案的贡献也就是该颜色成为最终颜色的概率。设 gig_igi 表示当前颜色成为最终颜色的概率有 g00g_00g00g11g_11g11且 gip×gi−1p×gi1(1−2p)×gig_{i}p\times g_{i-1}p\times g_{i1}(1-2p)\times g_igip×gi−1p×gi1(1−2p)×gi。 转化可得 gi−gi−1gi1−gig_i-g_{i-1}g_{i1}-g_{i}gi−gi−1gi1−gi等差数列求和可得 giisg_i\frac{i}{s}gisi即 visv\frac{i}{s}vsi。那么现在有fip×fi−1p×fi1(1−2p)×fiisf_ip\times f_{i-1}p\times f_{i1}(1-2p)\times f_i\frac{i}{s}fip×fi−1p×fi1(1−2p)×fisi转化后有fi−fi1fi−1−fis−1s−if_{i}-f_{i1}f_{i-1}-f_{i}\frac{s-1}{s-i}fi−fi1fi−1−fis−is−1考虑求 f1f_1f1 和 f2f_2f2 后线性递推由于 f0f_0f0 不存在代入后有 f22f1−1f_22f_1-1f22f1−1。 f1f1−fs∑i2sfi−1−fi(s−1)×(f1−f2)∑i2s−1s−1s−i×(s−i)(s−1)×(1−f1)(s−1)×(s−2)\begin{aligned}f_1f_1-f_s\\ \sum_{i2}^{s}{f_{i-1}-f_{i}}\\ (s-1)\times(f_1-f_2)\sum_{i2}^{s-1}{\frac{s-1}{s-i}\times(s-i)}\\(s-1)\times(1-f_1)(s-1)\times(s-2)\end{aligned}f1f1−fsi2∑sfi−1−fi(s−1)×(f1−f2)i2∑s−1s−is−1×(s−i)(s−1)×(1−f1)(s−1)×(s−2)所以f1(s−1)2sf_1\frac{(s-1)^2}{s}f1s(s−1)2线性递推即可求解答案为 ∑i1nfai\sum_{i1}^{n}{f_{a_{i}}}∑i1nfai。
Code
#includecstdio
using namespace std;
const int maxn100010,MLY1000000007;
int f[maxn],n,a[maxn],s,ans;
inline int power(int a,int b){int ans1;while(b){if(b1)ans1ll*ans*a%MLY;a1ll*a*a%MLY;b1;}return ans;
}
int main(){scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]),sa[i];f[1](s-1ll)*(s-1)%MLY*power(s,MLY-2)%MLY;f[2](2ll*f[1]-1MLY)%MLY;for(int i2;i100000;i)f[i1]((2ll*f[i]-f[i-1]-(s-1ll)*power(s-i,MLY-2))%MLYMLY)%MLY;for(int i1;in;i)ans(ansf[a[i]])%MLY;printf(%d,ans);return 0;
}
