题目描述：

小象喜欢为箱子涂色。小象现在有 c 种颜色，编号为 0~c-1；还有 n 个箱子，
编号为 1~n，最开始每个箱子的颜色为 1。小象涂色时喜欢遵循灵感：它将箱子
按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选
看做选 0 个），为之涂上随机一种颜色。若一个颜色为 a 的箱子被涂上 b 色，那
么这个箱子的颜色会变成（a*b）mod c。请问在 k 次涂色后，所有箱子颜色的编
号和期望为多少？

输入描述：

第一行为 T，表示有 T 组测试数据。
对于每组数据，第一行为三个整数 n,c,k。
接下来 k 行，每行两个整数 Li，Ri，表示第 i 个操作的 L 和 R。

输出描述：

对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留 9 位小数。

样例输入：

3
3 2 2
2 2
1 3
1 3 1
1 1
5 2 2
3 4
2 4

样例输出：

2.062500000
1.000000000
3.875000000

数据范围：

40%的数据 1<=T<=5，1<=n, k<=15，2<=c<=20；
100%的数据满足 1<=T<=10，1<=n, k<=50，2<=c<=100，1<=Li<=Ri<=n。

思路：

这其实是道DP题。。。
分别对每个箱子算贡献期望，再加起来
但是我一开始没想到，于是打了一个时间复杂度  2^( ( r-l )^k  )
于是他答案是正确的，可能等到人类灭绝都跑不出来

0分TLE代码 

/*
时间复杂度指数级增长  凉凉
*/
#include<bits/stdc++.h>
using namespace std;
int n,c,k;
int l[60],r[60];
int a[200];
int b[60][200];
double ans;
void dfs(int x,double gl)
{
	if(x==k+1)
	{
		int tot=0;
		for(int i=1;i<=n;i++)
			tot+=a[i];
		ans+=gl*tot;
		return;
	}
	for(int i=1;i<=n;i++)
		b[x][i]=a[i];
	for(int i=0;i<c;i++)//枚举颜色
	{
		short f[200];
		memset(f,0,sizeof(f));
		while(!f[r[x]+1])//枚举箱子
		{
			for(int j=1;j<=n;j++)//还原a
				a[j]=b[x][j];
			for(int j=l[x];j<=r[x];j++)//对a涂色
				if(f[j])
					a[j]=(a[j]*i)%c;
			dfs(x+1,(double)gl/(double)c/pow(2,r[x]-l[x]+1));
			int y=l[x];
			f[y]++;
			while(f[y]==2)//进位（类似2进制高精）
			{
				f[y+1]++;
				f[y]=0;
				y++;
			}
		}
	}
}
int main()
{
	freopen("elephant.in","r",stdin);
	freopen("elephant.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
		ans=0;
		cin>>n>>c>>k;
		for(int i=1;i<=n;i++)
			a[i]=1;
		for(int i=1;i<=k;i++)
			scanf("%d%d",&l[i],&r[i]);
		dfs(1,1);
		printf("%.9lf\n",ans);
	}
	return 0;
}

正解 

#include<bits/stdc++.h>
#pragma GCC target("f16c")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
using namespace std;
double dp[60][105][105];//存概率 
double ans;
int n,c,k,T;
int l[100],r[100];
int main()
{
	//freopen("elephant.in","r",stdin);
	//freopen("elephant.out","w",stdont);
	cin>>T;
	while(T--)
	{
		memset(dp,0,sizeof(dp));
		cin>>n>>c>>k;
		for(int i=1;i<=k;i++)
			scanf("%d %d",&l[i],&r[i]);
		for(int i=1;i<=n;i++)
			dp[i][0][1]=1;
		for(int i=1;i<=n;i++)//枚举每个箱子 
		{
			for(int j=1;j<=k;j++)//枚举第几次操作 
			{
				for(int ys=0;ys<c;ys++)//枚举现在的颜色(ys) 
				{
					for(int b=0;b<c;b++)//枚举涂的颜色 
					{
						if(i>=l[j]&&i<=r[j])//在操作区间 
						{
							//二分之一的概率改变颜色
							dp[i][j][(ys*b)%c]+=dp[i][j-1][ys]/2/c;
							// 二分之一的概率不改变颜色
							dp[i][j][ys]+=dp[i][j-1][ys]/2/c;
						}
						else//不在操作区间 
						{
							dp[i][j][ys]+=dp[i][j-1][ys]/c;
						}
					}
				}
			}
		}
		ans=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<c;j++)
				ans+=dp[i][k][j]*j;
		printf("%.9lf\n",ans);
	}
	return 0;
}