QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#885459 | #4228. Double Sort | jryggs | AC ✓ | 868ms | 441808kb | C++14 | 1.6kb | 2025-02-06 15:44:32 | 2025-02-06 15:44:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=55,M=1e4+5;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int n,m;
double jie[M],inv[M],f[N][M][2],g[N][M][N][2];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(),m=read();
jie[0]=inv[0]=1;
for(int i = 1;i<=n;i++)jie[i]=jie[i-1]*i,inv[i]=inv[i-1]/i;
f[0][0][1]=jie[n];
for(int i = 0;i<=n;i++){
for(int j = i;j<=m;j++){
if(f[i][j]==0)continue;
if(i&&i+j<=m){
f[i][i+j][1]=(f[i][i+j][1]+f[i][j][0]+f[i][j][1]);
for(int k = 1;k<=i;k++)g[i][j+i][k][1]=(g[i][i+j][k][1]+g[i][j][k][0]+f[i][j][0]+g[i][j][k][1]+f[i][j][1]);
}
for(int l = 1;l+i<=n;l++){
double w=f[i][j][1]*inv[l];
f[i+l][j+l][0]=(f[i+l][j+l][0]+w);
for(int k = i+1;k<=i+l;k++)g[i+l][j+l][k][0]=(g[i+l][j+l][k][0]+w);
}
for(int k = 1;k<=i;k++){
for(int l = 1;l+i<=n;l++)g[i+l][j+l][k][0]=(g[i+l][j+l][k][0]+g[i][j][k][1]*inv[l]);
}
}
}
long double ans=0,val=0;
for(int i = n;i<=m;i++){
long double now = 1;
for(int j = n;j<=i-1;j++)now*=j*1.0/(j-n+1);
val+=now;
}
for(int i = n;i>=1;i--){
for(int j = n;j<=m;j++){
ans=(ans+g[n][j][i][0]+g[n][j][i][1]);
// if(i==n)cout<<"!"<<j<<' '<<i<<' '<<g[n][j][i][0]+g[n][j][i][1]<<endl;
}
// cerr<<ans<<' '<<val<<endl;
printf("%.7Lf\n",ans/val);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5972kb
input:
3 5
output:
1.0000000 2.3000000 4.5000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5976kb
input:
5 17
output:
1.1313833 2.7483840 5.1830963 8.8556884 15.0000000
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 868ms
memory: 441808kb
input:
50 10000
output:
4.4328164 12.8365969 25.3152687 41.9556112 62.8480761 88.0871547 117.7716338 152.0048948 190.8952420 234.5562629 283.1072244 336.6735095 395.3871004 459.3871135 528.8203939 603.8421778 684.6168328 771.3186886 864.1329700 963.2568521 1068.9006549 1181.2892033 1300.6633810 1427.2819151 1561.4234346 17...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 7632kb
input:
40 40
output:
1.0000000 2.0000000 3.0000000 4.0000000 5.0000000 6.0000000 7.0000000 8.0000000 9.0000000 10.0000000 11.0000000 12.0000000 13.0000000 14.0000000 15.0000000 16.0000000 17.0000000 18.0000000 19.0000000 20.0000000 21.0000000 22.0000000 23.0000000 24.0000000 25.0000000 26.0000000 27.0000000 28.0000000 2...
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 39ms
memory: 56660kb
input:
39 1489
output:
1.5270876 3.9390126 7.3403302 11.7634937 17.2367014 23.7907109 31.4582877 40.2742331 50.2755910 61.5018753 73.9953247 87.8011951 102.9680948 119.5483709 137.5985586 157.1799042 178.3589798 201.2084094 225.8077337 252.2444474 280.6152553 311.0276071 343.6015935 378.4723167 415.7928925 455.7383104 498...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 758ms
memory: 411348kb
input:
47 9871
output:
4.8839176 14.2093220 28.0939348 46.6414310 69.9602358 98.1639517 131.3717230 169.7086511 213.3062527 262.3029666 316.8447148 377.0855261 443.1882307 515.3252374 593.6794038 678.4450160 769.8288950 868.0516496 973.3491032 1085.9739235 1206.1974945 1334.3120758 1470.6333079 1615.5031346 1769.2932338 1...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 75ms
memory: 84528kb
input:
9 9999
output:
111.5562226 348.0492604 727.3280018 1273.1900640 2018.9521113 3014.5891397 4343.3928098 6171.9464424 9000.0000000
result:
ok 9 numbers