彩色圆环

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;
}