【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-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用