国家集训队 彩色圆环
2022/2/14 6:12:13
本文主要是介绍国家集训队 彩色圆环,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
彩色圆环
Problem Statement
一个环上有\(n\)个点, 每个点随机染为\(m\)种颜色之一. 求换上同色连续长度之积的期望值.
Solution
先考虑链的情况: 设\(f_i\)表示考虑到第\(i\)位时的期望美观度, 按划分颜色块的思路\(DP\), 显然有\(f_i=\sum\limits_{0\leq j<i}f_j\times(i-j)\times P_{i-j}\times(M-1)\).
-
\(P_i\)表示连续选\(i\)个相同颜色的概率, \(P_i=M^{-i}\).
-
\((M-1)\)代表当前颜色块的颜色与前块不同的方案数, 无论前一种颜色如何, 都有\(M-1\)种方案.
利用圆环染色的思路来写环的\(DP\)式子
我们假设钦定了第\(0\)位的颜色. (其中第\(0\)位是我们虚构位置, 可以理解若我们将环, 破环为链后, 我们将链的前端和后端相同颜色块压缩到第\(0\)位, 然后环的问题就变成链的问题了, 当然去除前端和后端相同色块的链, 应当满足第一个色块与最后一个色块都不与\(0\)位的颜色相同, 值得注意的是我们压缩的块颜色标准为原先环颜色位置为\(1\)的颜色, 即如果\(1\)和\(N\)的颜色本身就不同, 我们只需将\(1\)颜色相同的块压缩到\(0\)位即可)
我们设\(f_{i,0/1}\)表示考虑前\(i\)位, 且要求第\(i\)位所属快的颜色是否与第\(0\)位颜色相同, 这时的期望美观度可得到转移方程: \(f_{i,0}=\sum\limits_{0\leq j<i}f_{j,0}\times(i-j)\times P_{i-j}\times(m-2)+f_{j,1}\times(i-j)\times P_{i-j}\times(m-1)\).\(f_{i,1}=\sum\limits_{0\leq j<i}f_{j,0}\times(i-j)\times P_{i-j}\).
其中第\(f_{i,0}\)的\(\sum\limits_{0\leq j<i}f_{j,0}\times(i-1)\times P_{i-j}\times(m-2)\)项中的\(m-2\)的含义为我既不能与前一块颜色相同, 也不能和第\(0\)块的颜色相同, 所以总共有\(m-2\)种方案可供选择. 后一项, 由于前一块的颜色与\(0\)的颜色相同, 所以总共有\(m-1\)种方案可供选择, 即我只要不选第\(0\)块的颜色即可.
\(f_{i,1}\)的含义为, 位置\(i\)的颜色与位置\(0\)的颜色一致, 显然前一块的颜色不能与位置\(0\)的颜色一样, 所以只能从\(f_{j,0}\)转移, 且\(i\)只能填与位置\(0\)颜色故转移系数为\(1\).
我们考虑求答案: 由于我们虚构了第\(0\)位, 我们已经把首尾相接颜色块压缩到位置\(0\)了, 我们只需要考虑剩下的链的链首与链尾的颜色与\(0\)不同即可.
那么\(Ans=P_n\times N\times M+\sum\limits_{1\leq x<N}x^2\times P_x\times M\times f_{n-x,0}\).
其中\(P_n\times N\times M\)项的含义是我长度为\(N\)的环, 每一个元素颜色均相同的期望贡献. 其中\(N\)为每种方案的贡献为\(N\), 总共有\(M\)种方案, 每种方案的概率为\(P_n\).
\(\sum\limits_{1\leq x<N}x^2\times P_x\times M\times f_{n-x,0}\). 含义是, 我假设我压缩首位相接颜色块的长度为\(x\), 那我们重新将它切割开总共有\(x\)种方案(假设切割成, \(x-y\)和\(y\)两个部分, 那我们将\(x-y\)放置链头, 和\(y\)放置链尾, 即可还原出原来的环, 特别地我们认为\(x=y\)或\(y=0\)是同一种方案)它的贡献对答案的贡献系数为其长度\(x\), 故得到\(x^2\)项, 由于第\(0\)块颜色可以有\(M\)种, 形成该块的概率为\(P_x\), 剩下首尾都不与\(0\)位相同的贡献系数为\(f_{n-x,0}\).
Code
# include "unordered_map" # include "algorithm" # include "iostream" # include "cstdlib" # include "cstring" # include "cstdio" # include "vector" # include "bitset" # include "queue" # include "cmath" # include "map" # include "set" using namespace std; const int maxm=2e5+10; long double DP[maxm][2]; long double P[maxm],Delt[maxm],Ans; int N,M; int main(){ static int i,j; scanf("%d%d",&N,&M); P[0]=1; for(i=1;i<=N;i++) P[i]=P[i-1]/M; DP[0][0]=0,DP[0][1]=1; for(i=1;i<=N;i++){ for(j=0;j<i;j++){ DP[i][0]+=DP[j][0]*(i-j)*P[i-j]*(M-2)+DP[j][1]*(i-j)*P[i-j]*(M-1); DP[i][1]+=DP[j][0]*(i-j)*P[i-j]; } } Ans=N*P[N]*M; for(i=1;i<N;i++) Ans+=i*i*P[i]*M*DP[N-i][0]; printf("%.5Lf",Ans); return 0; }
这篇关于国家集训队 彩色圆环的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南