题外话：其实还可以更优，用矩阵快速幂可以优化，也可以特征根推出通项公式，这里不展开讨论了

我们从中获取了一种处理环上dp的思路，即增设一维来维护首尾是否相同

先来看链的情况

设$f[i]$表示考虑到第$i$位时的期望美观度，显然有

$$f[i]=\sum_{0 \le j < i} f[j]*(i-j)*P[i-j]*(M-1)$$

其中$P[i]$表示连续选$i$个相同一种颜色的概率

$$P[i] = M^{-i}\\$$

那么现在用圆环染色的思路来试着写环的dp式

$f[i][0/1]$表示要决定的序列的前面（0位）已经确定了一种颜色，考虑到该序列第$i$位，且要求该位颜色与（1）/不与（0）0位颜色相同时，期望的美观度（许多题解对$f$的定义描述并不准确，实际上这里与圆环染色设置的状态有一点不同，就是实际上开头的颜色是不包含在我们要dp的那一段链中的。这关系到后面计算答案的正确性）

$$f[i][0] = \sum_{0 \le j < i} f[j][0]*(i-j)*P[i-j]*(m-2) + f[j][1]*(i-j)*P[i-j]*(m-1)\\ f[i][1] = \sum_{0 \le j < i} f[j][0]*(i-j)*P[i-j] $$

考虑如何求答案。考虑将首尾相接的那个颜色块的贡献单独拎出来计算。枚举首尾相接颜色块两端加起来的总长度$x$，则总共有$x$种分割首尾的方案，每种方案有$M$个颜色可以选择，每个方案贡献为$x$，剩下的部分就可以用$f$来表示了

$x=N$时要特判

$$Ans = P[N]*N*M + \sum_{1 \le x < N} x*x*P[x]*M*f[n-x][0] $$

$O(n^2)$的代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
typedef long double ldb;
typedef long long ll;
const ll MXN=1005;
ll N,M;
ldb f[MXN][2];
ldb P[MXN];
int main(){
    cin>>N>>M;
    P[0]=1;for(ll i=1;i<=N;i++) P[i]=P[i-1]/M;
    //f数组开两维，实际上是在与位于0位的虚拟颜色斗智斗勇，即f[i][0/1]表示：某一种颜色在序列的最前方（0位），最后一位是否与该颜色相同，美观程度的期望
    //这样设状态就给后面的答案计算提供了便捷
    f[0][0]=0;f[0][1]=1;//f[0][0]置0，是因为不能让f[i][1]直接从0转移
    for(ll i=1;i<=N;i++){
        f[i][0]=f[i][1]=0;
        for(ll j=0;j<i;j++){//可以从0转移，给了只有一个块转移的机会
            f[i][0]+=f[j][0]*(i-j)*P[i-j]*(M-2)
                    +f[j][1]*(i-j)*P[i-j]*(M-1);
            f[i][1]+=f[j][0]*(i-j)*P[i-j];
        }
    }
    ldb ans=N*P[N]*M;
    for(ll x=1;x<N;x++)
        ans+=x*x*P[x]*M*f[N-x][0];//一个x是贡献，一个x是分割开头和结尾的方式数，f[N-x][0]则充当了中间部分
    printf("%.5Lf",ans);
    return 0;
}

我们发现推出的dp方程有一部分是与$j$无关的。将它们提出来，维护剩下的只与$j$有关的前缀和，复杂度即可降至$O(N)$

前缀和优化后$O(n)$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
typedef long double ldb;
typedef long long ll;
const ll MXN=1000005;
ll N,M;
ldb f[MXN][2];
ldb powM[MXN];//M^i
int main(){
    cin>>N>>M;
    powM[0]=1;for(ll i=1;i<=N;i++) powM[i]=powM[i-1]*M;
    f[0][0]=0;f[0][1]=1;
    ldb s_01=0,s_0j=0;
    ldb s_11=1,s_1j=0;
    for(ll i=1;i<=N;i++){
        f[i][0] = s_01*(M-2)*i/powM[i] + s_0j*(M-2)/powM[i]
                + s_11*(M-1)*i/powM[i] + s_1j*(M-1)/powM[i];
        f[i][1] = s_01      *i/powM[i] + s_0j      /powM[i];
        s_01 += f[i][0]*powM[i];
        s_0j += f[i][0]*powM[i]*i;
        s_11 += f[i][1]*powM[i];
        s_1j += f[i][1]*powM[i]*i;
    }
    ldb ans=N/powM[N]*M;
    for(ll x=1;x<N;x++)
        ans+=x*x/powM[x]*M*f[N-x][0];
    printf("%.5Lf",ans);
    return 0;
}

实际上是会炸精度的，懒得管了:p