题目
小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择$[L,R]$这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成$(a*b)modc$ 。请问在k次涂色后，所有箱子颜色的编号和期望为多少？
分析
用$dp[i][j]$表示一个箱子染了$i$次后变成颜色$j$的概率
那么就有:
$$ dp[i][j]= egin{cases} dp[i+1][j]*2 \ (这次保持上一次的颜色j，即为不被染色) \ + \ dp[(i*k)mod_c][j]*2*c \ (这一次不保持j，被染色以及具体被染成了什么) end{cases} $$
（当然，递推的时候是要逆推的，如下）
$dp[i+1][j]+=dp[i][j]* $$frac{1}{2}$$ $
$dp[i+1][(j*kk)mod_c]+=dp[i][j]* $$frac{1}{2}$$ *$$frac{1}{c}$$ $
下面是参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,c,k;
int l,r,T;
int maxx,cnt[51];
double dp[51][101];
int main()
{
cin>>T;
while(T--)
{
memset(dp,0,sizeof(dp));
memset(cnt,0,sizeof(cnt));
cin>>n>>c>>k;
for(int i=1;i<=k;i++)
{
cin>>l>>r;
for(int j=l;j<=r;j++)
{
cnt[j]++;
maxx=max(cnt[j],maxx);
}
}
dp[0][1]=1;
for(int i=0;i<maxx;i++)
for(int j=0;j<c;j++)
{
dp[i+1][j]+=dp[i][j]/2;
for(int kk=0;kk<c;kk++)
dp[i+1][(j*kk)%c]+=dp[i][j]/2/c;
}
double ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<c;j++)
ans+=dp[cnt[i]][j]*j;
printf("%.9lf
",ans);
}
return 0;
}