题解

#include <bits/stdc++.h>
using namespace std;
int s[110];//s[i]表示第i个格子总共被涂色了几次（不涂也算一次） 
double f[110][110];//所有格子单独看待， f[i][j]表示染了i次色，变成j颜色的期望 
int main()
{
    int T;scanf("%d", &T);
    while(T--)
    {
        int n, c, K;scanf("%d%d%d", &n, &c, &K);
        memset(s, 0, sizeof(s));
        for(int i=1, x, y; i<=K; i++)scanf("%d%d", &x, &y), s[x] += 1, s[y+1] -= 1;
    
        int mmax = 0, tt = 0;for(int i=1; i<=n; i++)tt += s[i], s[i] = tt, mmax = max(mmax, tt);
         
        memset(f, 0, sizeof(f));f[0][1] = 1.0;//一开始全部都是1 
        for(int i=1; i<=mmax; i++) 
            for(int j=0; j<c; j++) 
            {
                f[i][j] += f[i-1][j] * 0.5;//有1/2的概率，不会被涂色
                for(int k=0; k<c; k++)f[i][(j*k)%c] += f[i-1][j] * (1.0/(2*c));//枚举所有可能被涂的颜色
                //被涂的概率是1/2，被涂k颜色概率为1/c，合起来就是1/(2*c) 
            }
             
        double ans = 0.0;
        for(int i=1; i<=n; i++)//枚举每一个箱子 
            for(int j=0; j<c; j++)//被涂成j颜色 
                ans += f[s[i]][j] * j;//i被涂有s[i]次，由于要求颜色和，乘以颜色 
        printf("%.9lf\n", ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int s[110];//s[i]表示第i个格子总共被涂色了几次（不涂也算一次） 
double f[110][110];//所有格子单独看待， f[i][j]表示染了i次色，变成j颜色的期望 
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,c,K;scanf("%d%d%d",&n,&c,&K);
        memset(s,0,sizeof(s));
        for(int i=1,x,y;i<=K;i++)scanf("%d%d",&x,&y),s[x]+=1,s[y+1]-=1;
    
        int mmax=0,tt=0;for(int i=1;i<=n;i++)tt+=s[i],s[i]=tt,mmax=max(mmax,tt);
         
        memset(f,0,sizeof(f));f[0][1]=1.0;//一开始全部都是1 
        for(int i=1;i<=mmax;i++) 
            for(int j=0;j<c;j++) 
            {
                f[i][j]+=f[i-1][j]*0.5;//有1/2的概率，不会被涂色
                for(int k=0;k<c;k++)f[i][(j*k)%c]+=f[i-1][j]*(1.0/(2*c));//枚举所有可能被涂的颜色
                //被涂的概率是1/2，被涂k颜色概率为1/c，合起来就是1/(2*c) 
            }
             
        double ans=0.0;
        for(int i=1;i<=n;i++)//枚举每一个箱子 
            for(int j=0;j<c;j++)//被涂成j颜色 
                ans+=f[s[i]][j]*j;//i被涂有s[i]次，由于要求颜色和，乘以颜色 
        printf("%.9lf\n",ans);
    }
    return 0;
}