2698: 染色
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 223 Solved: 150
[Submit][Status][Discuss]
Description
Input
输入一行四个整数，分别为N、M、S和T。
Output
输出一行为期望值，保留3位小数。
| 输出 | 5 1 2 3 | 染色一次共有7种等概率方案（题目描述中提到），其中染2个格子有4种，染3个格子有3种，期望值为2*4/7+3*3/7=2.429。 |
数据范围
1 ≤ S ≤ T ≤ N ≤ 1000000，0 ≤ M ≤ 1000000
题解：
/*ÎðÍü³õÐÄ£¬¾öÕ½¿ªÊ¼! */ #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #define N 1000005 using namespace std; double ans,p[N],tot; int n,m,s,t; int read() {int x=0,f=1; char ch;while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1;while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9');return x*f; } double fastpower(double x,int k) {double res=1.0;for (; k; k>>=1,x=x*x) if (k&1) res=res*x;return res; } double get(int x,int l,int r) {return 1.0*(x-l+1+x-r+1)*(r-l+1)/2; } int main() {n=read(); m=read(); s=read(); t=read();ans=0;tot=get(n,s,t);for (int i=s; i<=n; i++) p[i]+=get(i-1,s,min(i-1,t));for (int i=1; i<=n-s; i++) p[i]+=get(n-i,s,min(n-i,t));for (int i=1; i<=n; i++) ans+=1-fastpower(p[i]/tot,m);printf("%0.3lf",ans);return 0;}
