Description

　　大M成立的怪獸電力公司最近剛建立了一個網站。這個季度共有(n)天，第(i)天共有(v[i])個用戶點擊該網站，總的廣告價值為(c[i])。 然而大M并不知道該如何計算收入。他定義某一天的收入(（p[i]=min(100*max(v[i..j]),min(c[i..j]))（j>=i))。也許(j)不同會導致(p[i])不同，大M會選擇一個(j)使得(p[i])最大。

　　大M并不知道該如何算這個季度的每天平均收入。他會隨機在(n)天中選擇(k)天(i_1,i_2...i_k)，則這個季度的每天平均收入就定為(min(p[i_1],p[i_2]...p[i_k]))。 你作為他的會計對于他這種計算方法十分不放心。你想要知道在大M的計算下，這個季度的每天平均收入的期望值。

　　數據范圍：對于100%的數據，(n<=300000,k<=n,v[i]<=10^7,c[i]<=10^9)

Solution

　　首先我們假設我們已經求出了(p)，那么接下來的答案要怎么算?

?　　看到這種最大最小值貢獻類的題目。。感覺都有一個比較好的方向就是可以從某一個數作為最值然后反過來計算其貢獻

?　　比如說在這題里面就是，考慮每一個(p[i])會在多少中選擇中有貢獻，具體一點就是我們考慮將(p)按照從小到大的順序排列，然后依次從左往右考慮每一個(p[i])的貢獻

　　對于第(i)個位置的(p)值，因為這個位置要作為最小值才能有貢獻，所以(i)前面的數全部都不能選，所以也就是(inom {n-i} {k-1})種組合（第(i)這個位置的數確定要選，然后剩下的(k-1)個數只能在后面的(n-i)個數里面選），算概率的話就是除以一個總的方案數也就是(inom n k)即可

?　　那么現在的問題是，直接求組合數是不行的（沒有模數）

　　注意到每一個位置乘的系數那個組合數都是(inom x {k-1}/inom n k)的形式，然后當(x=n-1)的時候這個式子是(=k/n)的，然后我們發現對于不同的(i)，在改變的只有(x)，那我們把這個式子用階乘的形式寫開就發現它可以非常愉快地一路遞推回去了（每次(*(n-i-k+1)/(n-i))就可以了）

? 　　

　　然后現在的問題就只剩下怎么求(p)了

?　　我們觀察一下(p[i])的表達式，前半部分是取(max)（不遞減），后半部分是取(min)（不遞增），總的又是取(min)，稍微畫一下函數圖像之類的就可以發現能更新當前位置的方案一定是前面的(p)值或者令題目中的那個(j)等于當前位置時候表達式的取值

　　所以我們可以直接(O(n))dp一下得到(p)

　　然后這題就做完啦ovo

　　代碼大概長這個樣子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=300010;
int v[N],c[N],p[N];
long double ans,C;
int n,k;

int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
#endif
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i) scanf("%d",v+i);
	for (int i=1;i<=n;++i) scanf("%d",c+i);
	p[n]=min(v[n]*100,c[n]);
	for (int i=n-1;i>=1;--i){
		p[i]=max(p[i+1],100*v[i]);
		p[i]=min(p[i],c[i]);
	}
	sort(p+1,p+1+n);
	ans=0; C=(1.0*k)/(1.0*n);
	for (int i=1;n-i>=k-1;++i){
		ans+=1.0*p[i]*C;
		C*=(1.0*n-i-k+1)/(1.0*n-i);
	}
	printf("%.10Lf
",ans);
}
/*
input
3 2
3 2 1
300 200 300

output
133.333333
*/