【YBTOJ】【国家集训队】彩色圆环
2021/7/15 23:18:01
本文主要是介绍【YBTOJ】【国家集训队】彩色圆环,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
彩色圆环:
题目大意:
一个环上有 \(n\) 个点,每个点随机染为 \(m\) 种颜色之一。求环上同色连续段长度之积的期望值。
思路:
破环为链,就有 \(f_{i,[0,1]}\) 表示到第 \(i\) 个数,环首尾是否同种颜色的期望值。则有:
\[\begin{aligned} f_{i,1}&=\sum_{j=0}^{i-1} \frac{p_{i-j}\cdot f_{j,0} \cdot (i - j)}{m}\\ f_{i,0}&=\sum_{j=0}^{i-1} p_{i-j}\cdot (i - j)\left(\frac{(m-2)f_{i,0}}{m} + \frac{(m-1)f_{i,1}}{m}\right) \end{aligned}\]其中 \(p_i=m^{-i}\),即连续 \(i\) 个相同颜色的概率。
代码:
const int N = 210; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } double f[N][2], p[N], ans, m; int n; int main() { n = Read(); scanf ("%lf", &m); p[1] = 1.0; m = 1.0 / m; for (int i = 2; i <= n; i++) p[i] = p[i - 1] * m; f[0][1] = 1.0; for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) f[i][1] += p[i - j] * (i - j) * f[j][0] * m, f[i][0] += p[i - j] * (i - j) * (f[j][0] * (1 - 2 * m) + f[j][1] * (1 - m)); double ans = p[n] * n; for (int i = 1; i < n; i++) ans += 1.0 * i * i * f[n - i][0] * p[i]; //处理首尾不相接 printf ("%.10lf\n", ans); return 0; }
这篇关于【YBTOJ】【国家集训队】彩色圆环的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南