彩色圓環

金牌導航 期望-5

題目大意

給你一個環，每個位置的數字等概率為1~m中的其中一個，對于連續的相同數字的串，記其長度為$a_i$，求$a_i$的積的期望值

輸入樣例

8 1

輸出樣例

8.00000

數據范圍

$1?N?200,1?M?10^9$

解題思路

先預處理出出現連續x個相同數字的概率，記為prob
然后設$f_{i,1/0}$為前i個數中，第i個數和式子首尾相接的數相同/不同的期望值
那么有
$$\begin{array}{rl}{f}_{i,0}& +=f_{j,0}\times pro{b}_{i?j}\times (i?j)\times \frac{m?2}{m}\\ f_{i,0}& +=f_{j,1}\times pro{b}_{i?j}\times (i?j)\times \frac{m?1}{m}\\ f_{i,1}& +=f_{j,0}\times pro{b}_{i?j}\times (i?j)\times \frac{1}{m}\end{array}$$
i-j+1為貢獻值
第一行是既要不等于上一個又不等于收尾相接的
第二行是既要不等于上一個即可（因為首尾相接的和上一個相等）
第三行要和首尾相接的相等
最后處理一下首尾相接部分即可（詳情見代碼）

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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; }

總結

以上是生活随笔為你收集整理的【期望】彩色圆环（金牌导航 期望-5）的全部內容，希望文章能夠幫你解決所遇到的問題。

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