「NOIP模拟赛」小象涂色
题目描述:
小象喜欢为箱子涂色。小象现在有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
题解
若用f[i][j]表示第i个箱子染成颜色j,似乎复杂度比较奇怪
发现每个箱子是一样的,那么只要得出任意箱子染i次最终颜色j,就可以解决啦。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 2147483647 using namespace std; int read() { int 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 T; int n,c,K; int t[105]; double res,f[105][105],ans[105]; void dp() { for(int i=0;i<K;i++) { for(int x=0;x<c;x++) f[i+1][x]=f[i][x]/2; for(int x=0;x<c;x++) for(int y=0;y<c;y++) f[i+1][x*y%c]+=f[i][x]/c/2; } for(int i=0;i<=K;i++) for(int x=0;x<c;x++) ans[i]+=f[i][x]*x; } int main() { freopen("elephant.in","r",stdin); freopen("elephant.out","w",stdout); T=read(); while(T--) { memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans)); memset(t,0,sizeof(t)); res=0; n=read();c=read();K=read(); f[0][1]=1; dp(); for(int i=1;i<=K;i++) { int l=read(),r=read(); for(int j=l;j<=r;j++) t[j]++; } for(int i=1;i<=n;i++) res+=ans[t[i]]; printf("%.9lf\n",res); } return 0; } |
Subscribe