[HOJ 400] LOI

作法：

首先枚舉國手線的分數，還有哪些人落在國手線上，這時候就有一個這件事情發生的機率了，把他叫作 p 好了。再來對於落在線以外的人們，他們不是高於線就是低於線，並且高於線的人頂多只有 3 個。於是再對剩下的人枚舉有哪些人是高於線的，那麼這時候的機率就會變成： p * 那些人高於線的機率乘積 * 其他人低於線的機率乘積 ，那麼就可以把這個機率加到「高於線的那些人」的答案中。至於那些在線上的人，他們會抽籤爭奪 4 - num 個位置，其中 num 是高於線的人的數量，因此他們的機率必須還要再乘以 ( 4 - num ) / 線上人數，並且把他加到他們的答案中。在枚舉高於線的人的時候我是用DFS來做，然後因為時限看起來有點緊，所以我還先預處理「對於一個 i ，他的 bit 的位置分別是哪些」。而這題的另外一個重點就是機率的部份，我是先預處理出在 i 分中拿到 j 分的機率，並且在枚舉哪些人高於線哪些人低於線時，會必須要知道一個人高於某個分數或是低於某個分數的機率是多少，所以還必須要處理出機率的前綴和，也就是在 i 分中拿到 <= j 分的機率。而之後在詢問機率的時候，有可能會出現「詢問一個人在 i 分中拿到某個負數分」的機率是多少，所以如果直接查詢機率陣列會爛掉，所以另外用一個函式來寫這個東西，還有「在 i 分中拿到 x ~ y 分的機率」也會需要用函式寫，因為有可能 x 衝到負的，或是 y 衝的太大之類的，都會讓查表直接悲劇掉。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=12+2,maxm=400+10 ;
 
DB p[maxm][maxm],psum[maxm][maxm] ;
int n,m,a[maxn] ;
void cal_p()
{
    p[1][0]=p[1][1]=0.5 ;
    psum[1][0]=0.5 ; psum[1][1]=1.0 ;
    for(int i=2;i<=400;i++) for(int j=0;j<=i;j++)
    {
        if(j==0) p[i][j]=p[i-1][j]*0.5 ;
        else p[i][j]=(p[i-1][j-1]+p[i-1][j])*0.5 ;
        psum[i][j]= (j==0?p[i][j]:psum[i][j-1]+p[i][j]) ;
    }
}
 
DB getp(int x)
{
    if(x<0 || x>2*m) return 0 ;
    return p[2*m][x] ;
}
 
DB getpsum(int x,int y)
{
    x=max(x,0) ; y=min(y,2*m) ;
    if(y<x) return 0 ;
    return psum[2*m][y]-(x?psum[2*m][x-1]:0) ;
}
 
vector<int> bit[1<<maxn] ;
void cal_bit()
{
    for(int i=1;i<(1<<n);i++)
    {
        bit[i].clear() ;
        for(int j=0;j<n;j++) if(i&(1<<j))
            bit[i].push_back(j) ;
    }
}
 
int now[maxn],score ;
DB ans[maxn] ;
void dfs(int S,int x,int cnt,DB nowp)
{
    if(x==bit[S].size())
    {
        int num=n-__builtin_popcount(S) ;
        if(num+cnt<4) return ;
        for(int i=1;i<=cnt;i++) ans[now[i]]+=nowp ;
        for(auto i : bit[((1<<n)-1)^S])
            ans[i]+=nowp*((DB)4-cnt)/num ;
        return ;
    }
    if(nowp==0.0) return ;
    DB p1=getpsum(0,score-a[bit[S][x]]-1) ;
    DB p2=getpsum(score-a[bit[S][x]]+1,2*m) ;
    dfs(S,x+1,cnt,nowp*p1) ;
    if(cnt<3) now[cnt+1]=bit[S][x] , dfs(S,x+1,cnt+1,nowp*p2) ;
}
 
void calans()
{
    for(int i=1;i<(1<<n);i++) for(int j=4*m;j>=0;j--)
    {
        DB p0=1.0 ;
        for(auto k : bit[i]) p0*=getp(j-a[k]) ;
        if(p0==0.0) continue ;
        score=j ;
        dfs(((1<<n)-1)^i,0,0,p0) ;
    }
}
 
main()
{
    cal_p() ;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cal_bit() ;
        for(int i=0;i<n;i++)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            a[i]=x+y ;
        }
        memset(ans,0,sizeof(ans)) ;
        calans() ;
        for(int i=0;i<n;i++) printf("%.10f\n",ans[i]) ;
    }
}