QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791272 | #9300. So Many Possibilities... | IllusionaryDominance# | WA | 872ms | 136836kb | C++14 | 1.8kb | 2024-11-28 17:46:59 | 2024-11-28 17:47:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using ll = long long;
using db = long double;
const int N = 105;
db f[105][1<<16], g[106][1<<16];
ll all, n, m, popcnt[1<<16];
ll sum[1<<16];
ll a[105];
db c[N][N];
void init()
{
c[0][0] = 1;
for (int i = 1; i < N; ++i)
{
c[i][0] = c[i][i] = 1;
for (int j = 1; j < N; ++j) c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
db C(int x, int y)
{
if (x < 0 || y < 0 || x < y) return 0;
return c[x][y];
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m; init();
for (int i = 1; i <= n; ++i) cin >> a[i];
all = (1<<n) - 1;
for (int i = 1; i <= all; ++i)
{
popcnt[i] = __popcount(i);
sum[i] = sum[i - (i&-i)] + a[__lg(i&-i) + 1];
}
f[0][0] = 1;
for (int i = 1; i <= m; ++i) f[i][0] = f[i-1][0] / n;
g[0][0] = 1;
for (int s = 1; s <= all; ++s)
{
int ss = s - (s&-s), id = __lg(s&-s) + 1;
for (int i = 0; i < a[id]; ++i)
for (int j = 0; j + i <= m; ++j)
g[i+j][s] += g[j][ss] * C(i+j, i);
}
for (int s = 1; s <= all; ++s)
{
for (int i = 1; i <= n; ++i) for (int step = 1; step <= m; ++step) if (s>>(i-1) & 1)
{
f[step][s] += f[step-1][s - (1<<(i-1))] * C(step - sum[s - (1<<(i-1))] - 1, a[i] - 1) / (n - popcnt[s] + 1);
}
for (int i = 1; i <= m; ++i) f[i][s] += f[i-1][s] / (n - popcnt[s]);
}
db ans = 0;
for (int s = 1; s <= all; ++s) if (m >= sum[s])
{
// cerr << s << " " << popcnt[s] << " " << f[m][s] << " " << g[m-sum[s]][all-s] << " "<< sum[s] << "\n";
ans += popcnt[s] * f[m][s] * g[m - sum[s]][all - s];
}
cout << fixed << setprecision(16) << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10228kb
input:
2 2 2 2
output:
0.5000000000000000
result:
ok found '0.5000000000', expected '0.5000000000', error '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 10144kb
input:
3 3 1 2 3
output:
1.0833333333333333
result:
ok found '1.0833333333', expected '1.0833333333', error '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 31312kb
input:
3 100 80 32 38
output:
0.9176820175127025
result:
ok found '0.9176820175', expected '0.9176820175', error '2.22045e-16'
Test #4:
score: 0
Accepted
time: 0ms
memory: 17128kb
input:
4 100 31 80 40 28
output:
0.3896011367171476
result:
ok found '0.3896011367', expected '0.3896011367', error '0'
Test #5:
score: 0
Accepted
time: 7ms
memory: 19840kb
input:
8 100 37 42 41 43 52 24 7 21
output:
0.9966505480130125
result:
ok found '0.9966505480', expected '0.9966505480', error '2.22045e-16'
Test #6:
score: 0
Accepted
time: 6ms
memory: 28732kb
input:
9 100 6 13 4 6 20 13 10 25 25
output:
5.7555476550210278
result:
ok found '5.7555476550', expected '5.7555476550', error '8.88178e-16'
Test #7:
score: 0
Accepted
time: 4ms
memory: 18508kb
input:
10 10 6 5 6 10 9 6 10 7 1 9
output:
0.6537136478862566
result:
ok found '0.6537136479', expected '0.6537136479', error '0'
Test #8:
score: 0
Accepted
time: 210ms
memory: 68756kb
input:
15 50 6 5 9 1 3 3 10 19 16 18 10 12 16 14 6
output:
3.0389711621720845
result:
ok found '3.0389711622', expected '3.0389711622', error '0'
Test #9:
score: 0
Accepted
time: 872ms
memory: 136836kb
input:
15 100 80 42 42 99 93 31 22 48 37 58 77 96 5 87 79
output:
0.8039483745624001
result:
ok found '0.8039483746', expected '0.8039483746', error '2.22045e-16'
Test #10:
score: 0
Accepted
time: 0ms
memory: 51568kb
input:
3 50 34 30 36
output:
0.0001006171025852
result:
ok found '0.0001006171', expected '0.0001006171', error '0'
Test #11:
score: 0
Accepted
time: 8ms
memory: 53824kb
input:
10 90 10 11 9 10 10 8 11 13 8 9
output:
6.3826275798730052
result:
ok found '6.3826275799', expected '6.3826275799', error '2.66454e-15'
Test #12:
score: 0
Accepted
time: 50ms
memory: 61760kb
input:
12 100 12 13 10 11 11 14 14 10 7 8 4 8
output:
5.7844511712887842
result:
ok found '5.7844511713', expected '5.7844511713', error '1.77636e-15'
Test #13:
score: 0
Accepted
time: 493ms
memory: 129464kb
input:
15 100 12 11 12 10 15 12 7 6 12 5 11 7 10 11 9
output:
3.8508740133812733
result:
ok found '3.8508740134', expected '3.8508740134', error '8.88178e-16'
Test #14:
score: 0
Accepted
time: 457ms
memory: 136676kb
input:
15 100 7 7 6 4 11 8 12 8 5 7 9 8 10 8 15
output:
7.8130842395242610
result:
ok found '7.8130842395', expected '7.8130842395', error '3.55271e-15'
Test #15:
score: 0
Accepted
time: 12ms
memory: 62140kb
input:
10 95 8 11 6 14 6 5 11 14 10 14
output:
8.1380514910188204
result:
ok found '8.1380514910', expected '8.1380514910', error '1.77636e-15'
Test #16:
score: 0
Accepted
time: 51ms
memory: 68372kb
input:
12 93 4 8 6 8 12 8 10 6 8 8 13 9
output:
9.1200096759309450
result:
ok found '9.1200096759', expected '9.1200096759', error '3.55271e-15'
Test #17:
score: 0
Accepted
time: 456ms
memory: 134668kb
input:
15 99 9 5 8 4 9 7 4 6 7 7 5 6 8 8 7
output:
14.0000000000000000
result:
ok found '14.0000000000', expected '14.0000000000', error '5.32907e-15'
Test #18:
score: -100
Wrong Answer
time: 380ms
memory: 122376kb
input:
15 88 6 3 8 4 5 6 6 5 10 6 4 7 8 3 7
output:
-nan
result:
wrong output format Expected double, but "-nan" found