QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712557#6565. Game Show Eliminationucup-team902AC ✓694ms89544kbC++203.8kb2024-11-05 16:09:152024-11-05 16:09:16

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 16:09:16]
  • 评测
  • 测评结果:AC
  • 用时:694ms
  • 内存:89544kb
  • [2024-11-05 16:09:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using db=long double;
const int N=1024,K=1<<9;
const db eps=1e-12;
int n,k;
db g[12][K+5][12],f[N+5][12][K+5];
db ans[N+5];
int getv(int x,int d){
    return x==k?0:x==k+1?d:-x-1;
}
db work(int d,int s,int pos,int mx){
    if(pos==mx) return 0;
    mx=getv(mx,d);
    pos=getv(pos,d);
    static db h[12];
    db res=0;
    for(int v=pos;v<pos+k;v++){
        memset(h,0,sizeof h);
        h[0]=1;
        for(int i=0;i<=k+1;i++)
            if((s>>i&1)||(i>=k)){
                int vi=getv(i,d);
                if(vi==pos) continue;
                if(vi!=mx){
                    if(v<vi)
                        memset(h,0,sizeof h);
                    else if(v<vi+k){
                        for(int j=k;j;j--)
                            h[j]=h[j-1]+(v-vi)*h[j];
                        h[0]*=(v-vi);
                        for(int j=0;j<=k;j++) h[j]/=k;
                    }
                }
                else{
                    if(v>=vi+k)
                        memset(h,0,sizeof h);
                    else if(v>=vi){
                        for(int j=k;j;j--)
                            h[j]=h[j]*(vi+k-v)-h[j-1];
                        h[0]*=(vi+k-v);
                        for(int j=0;j<=k;j++) h[j]/=k;
                    }
                }
            }
        for(int i=0;i<=k;i++)
            res+=h[i]/(i+1);
    }
    return res/k;
}
void prep(){
    for(int i=1;i<=k;i++)
        for(int s=0;s<(1<<k-1);s++){
            for(int j=0;j<=k+1;j++){
                if((s>>j&1)||j>=k){
                    int mx;
                    for(mx=0;mx<k;mx++)
                        if((s>>mx&1)&&(-mx-1+k>i))
                            g[i][s][j]+=work(i,s,j,mx);
                    g[i][s][j]+=work(i,s,j,k);
                    g[i][s][j]+=work(i,s,j,k+1);
                }
            }
        }
}
int popc(int s){
    int res=0;
    for(;s;s&=s-1) res++;
    return res;
}
int main(){
    scanf("%d %d",&n,&k);
    prep();
    f[n-1][1][(1<<min(k-1,n-2))-1]=1;
    for(int i=n-1;i;i--){
        int rk=min(i-1,k-1);
        for(int j=1;j<=k;j++){
            for(int s=(1<<rk)-1;s>=0;s--){
                int crk=i-rk+1+popc(s);
                for(int l=0;l<rk;l++)
                    if(s>>l&1){
                        db c=f[i][j][s]*g[j][s][l];
                        ans[i-l-1]+=c*crk;
                        f[i][j][s^(1<<l)]+=c;
                    }
                if(crk==2){
                    db c1=f[i][j][s]*g[j][s][k];
                    db c2=f[i][j][s]*g[j][s][k+1];
                    ans[i]+=c1*2+c2;
                    if(j<k)
                        ans[i+j]+=c2*2+c1;
                }
                else{
                    int ni=i-1,ns=s|(1<<k-1);
                    while(1){
                        if(ns&1){
                            ns>>=1;
                            break;
                        }
                        ni--;
                        ns=(ns>>1)|(1<<k-1);
                    }
                    ns&=(1<<min(ni-1,k-1))-1;
                    db c=f[i][j][s]*g[j][s][k];
                    ans[i]+=c*crk;
                    int nd=i+j-ni;
                    if(j<k&&nd>=k)
                        ans[i+j]+=c;
                    nd=min(nd,k);
                    f[ni][nd][ns]+=c;
                    if(j<k){
                        c=f[i][j][s]*g[j][s][k+1];
                        nd=i-ni;
                        ans[i+j]+=c*crk;
                        if(nd>=k)
                            ans[i]+=c;
                        f[ni][nd][ns]+=c;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%.13LF\n",ans[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3940kb

input:

3 2

output:

2.1093750000000
2.6250000000000
1.2656250000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 694ms
memory: 89544kb

input:

1000 10

output:

2.9272933166112
3.5373161568760
4.2811822033069
5.1312206601865
6.0539327790165
7.0191885098663
8.0057023991095
9.0012910303480
10.0001652076757
11.0000000000000
12.0000000000000
13.0000000000000
14.0000000000000
15.0000000000000
16.0000000000000
17.0000000000000
18.0000000000000
19.0000000000000
20...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 39ms
memory: 20172kb

input:

300 8

output:

2.7512630513322
3.3900737270548
4.1750068650797
5.0660215194411
6.0201465578408
7.0045578588980
8.0005725930652
9.0000000000000
10.0000000000000
11.0000000000000
12.0000000000000
13.0000000000000
14.0000000000000
15.0000000000000
16.0000000000000
17.0000000000000
18.0000000000000
19.0000000000000
20...

result:

ok 300 numbers

Test #4:

score: 0
Accepted
time: 4ms
memory: 17952kb

input:

1000 3

output:

2.2302561681029
3.0347656711132
4.0000000000000
5.0000000000000
6.0000000000000
7.0000000000000
8.0000000000000
9.0000000000000
10.0000000000000
11.0000000000000
12.0000000000000
13.0000000000000
14.0000000000000
15.0000000000000
16.0000000000000
17.0000000000000
18.0000000000000
19.0000000000000
20...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 294ms
memory: 5104kb

input:

7 10

output:

2.9815864383718
3.4936049601181
3.9653422649127
4.3196770585875
4.5087248562227
4.4988808476505
4.2321835741366

result:

ok 7 numbers

Test #6:

score: 0
Accepted
time: 224ms
memory: 77292kb

input:

993 9

output:

2.8411212285174
3.4643592446426
4.2273243674465
5.0969425981705
6.0352816658084
7.0105742428138
8.0023873942439
9.0003025183896
10.0000000000000
11.0000000000000
12.0000000000000
13.0000000000000
14.0000000000000
15.0000000000000
16.0000000000000
17.0000000000000
18.0000000000000
19.0000000000000
20...

result:

ok 993 numbers