2698: 染色
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 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=,f=; char ch;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
return x*f;
}
double fastpower(double x,int k)
{
double res=1.0;
for (; k; k>>=,x=x*x) if (k&) res=res*x;
return res;
}
double get(int x,int l,int r)
{
return 1.0*(x-l++x-r+)*(r-l+)/;
}
int main()
{
n=read(); m=read(); s=read(); t=read();
ans=;
tot=get(n,s,t);
for (int i=s; i<=n; i++) p[i]+=get(i-,s,min(i-,t));
for (int i=; i<=n-s; i++) p[i]+=get(n-i,s,min(n-i,t));
for (int i=; i<=n; i++) ans+=-fastpower(p[i]/tot,m);
printf("%0.3lf",ans);
return ; }