惠州企业建站系统,今天时事新闻,湖南省住房和城乡建设部网站,百度软件下载安装彩色圆环
金牌导航 期望-5
题目大意
给你一个环#xff0c;每个位置的数字等概率为1~m中的其中一个#xff0c;对于连续的相同数字的串#xff0c;记其长度为aia_iai#xff0c;求aia_iai的积的期望值
输入样例
8 1输出样例
8.00000数据范围 1⩽N⩽200,1⩽M⩽109…彩色圆环
金牌导航 期望-5
题目大意
给你一个环每个位置的数字等概率为1~m中的其中一个对于连续的相同数字的串记其长度为aia_iai求aia_iai的积的期望值
输入样例
8 1输出样例
8.00000数据范围
1⩽N⩽200,1⩽M⩽1091\leqslant N \leqslant 200,1\leqslant M \leqslant 10^91⩽N⩽200,1⩽M⩽109
解题思路
先预处理出出现连续x个相同数字的概率记为prob 然后设fi,1/0f_{i,1/0}fi,1/0为前i个数中第i个数和式子首尾相接的数相同/不同的期望值 那么有 fi,0fj,0×probi−j×(i−j)×m−2mfi,0fj,1×probi−j×(i−j)×m−1mfi,1fj,0×probi−j×(i−j)×1m\begin{aligned}f_{i,0} f_{j,0} \times prob_{i - j} \times (i - j) \times \frac{m-2}{m}\\f_{i,0} f_{j,1} \times prob_{i - j} \times (i - j) \times \frac{m-1}{m}\\f_{i,1} f_{j,0} \times prob_{i - j} \times (i - j) \times \frac{1}{m}\end{aligned}fi,0fi,0fi,1fj,0×probi−j×(i−j)×mm−2fj,1×probi−j×(i−j)×mm−1fj,0×probi−j×(i−j)×m1 i-j1为贡献值 第一行是既要不等于上一个又不等于收尾相接的 第二行是既要不等于上一个即可因为首尾相接的和上一个相等 第三行要和首尾相接的相等 最后处理一下首尾相接部分即可详情见代码
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int n;
double m, ans, prob[210], f[210][2];
int main()
{scanf(%d%lf, n, m);prob[1] 1;f[0][1] 1;for (int i 2; i n; i)prob[i] prob[i - 1] / m;//求概率for (int i 1; i n; i)for(int j 0; j i; j){f[i][0] f[j][0] * prob[i - j] * (i - j) * (m - 2) / m;f[i][0] f[j][1] * prob[i - j] * (i - j) * (m - 1) / m;f[i][1] f[j][0] * prob[i - j] * (i - j) / m;}ans n * prob[n];for (int i 1; i n; i)ans f[i][0] * prob[n - i] * (n - i) * (n - i);//首尾相接的以保证不相等不用除第一个n-i为贡献第二个为把最后面的移到前面的方案数printf(%.5lf, ans);return 0;
}
