标签：数学期望，DP
题目描述
虽然不知道为什么，但是你一直想用一种神奇的方式完成一幅画作。
你把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的期望值等于。
输入格式
第一行包含3个正整数n, c, k，意义如题所述。
接下来k行，每行包含两个数Li, Ri，表示你每次操作会从哪个区间内随机地选画纸。
输出格式
一行，一个小数，表示答案，四舍五入精确到小数点后3位。
样例输入1
2 3 1
1 2
样例输出1
2.000
样例解释
一共有4种选择子集的可能，每种的概率都是。
选空集：画纸不会发生改变，颜色和是1+1=2；
选{1}：画纸2不会发生改变。选颜色有3种可能，使得画纸1最终分别变成颜色0、1、2，概率都是，颜色和的期望是；
选{2}：与选1对称，颜色和的期望也是2；
选{1,2}：选颜色有3种可能，使得两张画纸最终都变成颜色0、1、2，概率都是，颜色和的期望是；
综上，4种选择子集的方案的颜色和的期望为。
样例输入2
3 3 3
1 2
2 3
1 3
样例输出2
2.639
数据范围
|
测试点编号 |
n |
k |
c |
其它 |
|
1 |
≤10 |
=1 |
≤10 |
|
|
2 |
|
|||
|
3 |
≤100 |
≤100 |
|
|
|
4 |
|
|||
|
5 |
=1 |
≤100 |
Li=Ri |
|
|
6 |
≤100 |
|||
|
7 |
|
|||
|
8 |
|
|||
|
9 |
|
|||
|
10 |
|
对所有数据，1≤Li≤Ri ≤n。
分析：
第一眼看到题，样例2手玩不出来gg
貌似只会打20分的暴力，毕竟没怎么做过期望题
其实是很简单的一个有关期望的性质
和的期望=期望的和 就是期望的可加性啦
正解做法和50分部份分做法类似
DP
F[i][j]表示涂i次后显示颜色j的概率
转移：f[i+1][j*t%c]+=f[i][j]/c
G[i][j]表示i次被包含在区间里，j次被选中的概率（就是C(i，j)/2i）
G[i][j]=(g[i-1][j]+g[i-1][j-1])/2
Ans=
对于满分的做法，我们用Cnt数组记录下每个画纸被覆盖的次数
用和之前一样的做法去计算
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define eps 1e-7
using namespace std;
inline ll read()
{
ll f=1,x=0;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;
}
const int maxn=106;
int k,n,cnt[maxn],mx,c;
double ans,g[maxn][maxn],f[maxn][maxn];
int main()
{
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
g[0][0]=1;
rep(i,0,100)
rep(j,0,i){g[i+1][j]+=g[i][j]/2.0;g[i+1][j+1]+=g[i][j]/2.0;}
n=read(),c=read(),k=read();
mem(cnt,0);mx=0;
rep(i,1,k){
int x=read(),y=read();
rep(j,x,y){
cnt[j]++;
mx=max(mx,cnt[j]);
}
}
mem(f,0);
f[0][1]=1;
rep(i,0,mx-1)
rep(j,0,c-1)
if(f[i][j]>eps)
rep(r,0,c-1)f[i+1][j*r%c]+=f[i][j]/c;
ans=0;
rep(i,1,n)
rep(j,0,cnt[i])
rep(r,0,c-1)ans+=g[cnt[i]][j]*f[j][r]*r;
printf("%.3lf\n",ans);
return 0;
}
