灵魂画师
题目描述
虽然不知道为什么，但是你一直想用一种神奇的方式完成一幅画作。
你把n张画纸铺成一排，并将它们从1到n编号。你一共有c种颜色可用，这些颜色可以用0到c-1来编号。初始时，所有画纸的颜色都为1。你一共想进行k次作画，第i次作画时，你会等概率随机地选闭区间[Li,Ri]内的画纸的一个子集（可以为空），再随机挑一种颜色bi，并把挑出来的画纸都涂上该颜色。原有颜色a的画纸在涂上颜色b后，颜色会变成(a*b) mod c，这是这个世界的规律。
因为你将颜色用数字来命名了，因此你可以求出在k次作画结束后，每张画纸上的颜色对应的数字相加之和的期望。现在请你编程求一下这个值。
以防万一你不知道什么是期望：如果一个量X，它有p1的概率值为v1，有p2的概率值为v2……pn的概率值为vn，则X的期望值等于p1v1+p2v2+……+pnvn
输入格式
第一行包含3个正整数n, c, k，意义如题所述。
接下来k行，每行包含两个数Li, Ri，表示你每次操作会从哪个区间内随机地选画纸。
输出格式
一行，一个小数，表示答案，四舍五入精确到小数点后3位。
样例输入1
2 3 1 1 2
样例输出1
2.000
样例解释
一共有4种选择子集的可能，每种的概率都是1/4。
选空集：画纸不会发生改变，颜色和是1+1=2；
选{1}：画纸2不会发生改变。选颜色有3种可能，使得画纸1最终分别变成颜色0、1、2，概率都是1/3，颜色和的期望是1/3*(0+1)+1/3*(1+1)+1/3*(2+1)=2；
选{2}：与选1对称，颜色和的期望也是2；
选{1,2}：选颜色有3种可能，使得两张画纸最终都变成颜色0、1、2，概率都是1/3，颜色和的期望是1/3*(0+0)+1/3*(1+1)+1/3*(2+2)=2；
综上，4种选择子集的方案的颜色和的期望为2。
样例输入2
3 3 3 1 2 2 3 1 3
样例输出2
2.639
数据范围：
思路：
和的期望=期望的和。由于每张纸的初始状态都是1，所以考虑N3的期望DP。我们用dp[i][j]表示一张纸被操作了i次之后变成颜色j的概率。对每张纸单独计算，统计操作了几次。在每次枚举子集时，区间内的每个元素都有二分之一的概率被选中上色，而每种颜色被选中的概率是1/c，然后我们就有了转移方程，如果被选上：dp[t][i*j%c]+=dp[t-1][i]/(c*2);如果没被选上：dp[t][i]+=dp[t-1][i]/2;
代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,c,k,a,b,num[108],maxn; double dp[108][108],ans; long long read() { long long x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); n=read();c=read();k=read(); for(int i=1;i<=k;++i) { a=read();b=read(); for(int i=a;i<=b;++i) { num[i]++; maxn=max(maxn,num[i]); } } dp[0][1]=1; for(int t=1;t<=maxn;++t) { for(int i=0;i<c;++i) { for(int j=0;j<c;++j) { dp[t][i*j%c]+=dp[t-1][i]/(c*2); } dp[t][i]+=dp[t-1][i]/2; } } for(int i=1;i<=n;++i) { for(int j=0;j<c;++j) { ans+=dp[num[i]][j]*j; } } printf("%.3lf",ans); return 0; }