QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370234 | #4228. Double Sort | InfinityNS# | AC ✓ | 72ms | 27868kb | C++14 | 1.6kb | 2024-03-28 23:18:53 | 2024-03-28 23:18:55 |
Judging History
answer
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ld long double
using namespace std;
const int N=51,M=10001;
ld nck[M+N][N];
ld nckSum[M+N][N];
ld dp[N][M];
ld ways[N][M];
ld ans[N];
int main(){
int n,m;
scanf("%i %i",&n,&m);
for(int k=0;k<=m+n;k++){
for(int j=0;j<=n;j++){
if(j>k)nck[k][j]=0;
else{
if(k==0||j==0)nck[k][j]=1;
else{
nck[k][j]=nck[k-1][j-1]+nck[k-1][j];
}
}
}
}
for(int i=0;i<=m+n;i++){
for(int j=0;j<=n;j++){
nckSum[i][j]=nck[i][j];
if(i)
nckSum[i][j]+=nckSum[i-1][j];
//printf("%i %i: %Lf\n",i,j,nckSum[i][j]);
}
}
ways[n][m]=1;
for(int sum=m;sum>=0;sum--){
for(int i=1;i<=n;i++){
if(sum<i)continue;
for(int g=0;g<=i;g++){
ways[i-g][sum-i]+=nck[i][g]*ways[i][sum];
}
}
}
for(int sum=0;sum<=m;sum++){
for(int i=1;i<=n;i++){
if(sum<i)continue;
ld ww=nckSum[sum-1][i-1];
//printf("%i %i: %Lf\n",i,sum,ww);
ww*=ways[i][sum];
//printf("%i %i: %Lf\n",i,sum,ways[i][sum]);
for(int j=0;j<i;j++){
ans[j]+=ww;
}
}
}
ld ww=nckSum[m-1][n-1];
for(int i=0;i<n;i++){
ans[i]/=ww;
}
for(int i=n-2;i>=0;i--){
ans[i]+=ans[i+1];
}
for(int i=n-1;i>=0;i--){
printf("%.10Lf\n",ans[i]);
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3960kb
input:
3 5
output:
1.0000000000 2.3000000000 4.5000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
5 17
output:
1.1313833226 2.7483839690 5.1830963154 8.8556884292 15.0000000000
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 72ms
memory: 27868kb
input:
50 10000
output:
4.4328164335 12.8365968668 25.3152687339 41.9556112383 62.8480760618 88.0871546758 117.7716337788 152.0048947778 190.8952420036 234.5562629251 283.1072243847 336.6735094732 395.3871003913 459.3871135128 528.8203938988 603.8421777570 684.6168328365 771.3186885683 864.1329699727 963.2568520715 1068.90...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 4240kb
input:
40 40
output:
1.0000000000 2.0000000000 3.0000000000 4.0000000000 5.0000000000 6.0000000000 7.0000000000 8.0000000000 9.0000000000 10.0000000000 11.0000000000 12.0000000000 13.0000000000 14.0000000000 15.0000000000 16.0000000000 17.0000000000 18.0000000000 19.0000000000 20.0000000000 21.0000000000 22.0000000000 2...
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 8ms
memory: 7328kb
input:
39 1489
output:
1.5270875628 3.9390125652 7.3403302435 11.7634937450 17.2367013630 23.7907109205 31.4582877129 40.2742330903 50.2755910473 61.5018753030 73.9953246967 87.8011951264 102.9680947788 119.5483709315 137.5985586446 157.1799042332 178.3589797787 201.2084093701 225.8077336763 252.2444474329 280.6152553480 ...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 63ms
memory: 27188kb
input:
47 9871
output:
4.8839175854 14.2093220216 28.0939348059 46.6414309717 69.9602357807 98.1639517434 131.3717230464 169.7086510733 213.3062526631 262.3029665937 316.8447148205 377.0855260737 443.1882307257 515.3252374057 593.6794037510 678.4450160011 769.8288949916 868.0516496140 973.3491031658 1085.9739234660 1206.1...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 7ms
memory: 21324kb
input:
9 9999
output:
111.5562225553 348.0492603945 727.3280017986 1273.1900640301 2018.9521112541 3014.5891397187 4343.3928098375 6171.9464424375 9000.0000000000
result:
ok 9 numbers