QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791301#9300. So Many Possibilities...IllusionaryDominance#AC ✓948ms144648kbC++141.9kb2024-11-28 17:57:392024-11-28 17:57:40

Judging History

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

  • [2024-11-28 17:57:40]
  • 评测
  • 测评结果:AC
  • 用时:948ms
  • 内存:144648kb
  • [2024-11-28 17:57:39]
  • 提交

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 = 205;
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 < i; ++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))] / (n - popcnt[s] + 1) * C(step - sum[s - (1<<(i-1))] - 1, a[i] - 1);
        }
        if (n - popcnt[s]) for (int i = 1; i <= m; ++i) f[i][s] += f[i-1][s] / (n - popcnt[s]);
    }
    __float128 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];
    }
    long double Ans = (long double)ans;
    cout << fixed << setprecision(16) << Ans << "\n";
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10612kb

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: 10712kb

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: 62552kb

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: 47992kb

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: 62936kb

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: 4ms
memory: 49388kb

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: 0ms
memory: 17024kb

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: 314ms
memory: 84244kb

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: 900ms
memory: 144244kb

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: 59956kb

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: 12ms
memory: 76476kb

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: 63ms
memory: 85252kb

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: 547ms
memory: 144648kb

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: 438ms
memory: 136976kb

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: 13ms
memory: 76560kb

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: 48ms
memory: 82296kb

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: 418ms
memory: 129528kb

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: 0
Accepted
time: 460ms
memory: 131604kb

input:

15 88
6 3 8 4 5 6 6 5 10 6 4 7 8 3 7

output:

15.0000000000000000

result:

ok found '15.0000000000', expected '15.0000000000', error '5.32907e-15'

Test #19:

score: 0
Accepted
time: 0ms
memory: 18892kb

input:

5 10
18 68 13 47 14

output:

0.0000000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Test #20:

score: 0
Accepted
time: 23ms
memory: 67980kb

input:

10 80
92 91 100 87 88 88 100 87 94 93

output:

0.0000000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Test #21:

score: 0
Accepted
time: 647ms
memory: 110804kb

input:

15 80
93 87 84 83 91 95 83 84 98 93 88 95 81 92 99

output:

0.0000000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Test #22:

score: 0
Accepted
time: 0ms
memory: 47912kb

input:

5 100
14 89 6 98 11

output:

2.9997413382376274

result:

ok found '2.9997413382', expected '2.9997413382', error '4.44089e-16'

Test #23:

score: 0
Accepted
time: 11ms
memory: 44608kb

input:

10 100
1 5 4 1 5 4 2 87 3 4

output:

9.0000000000000000

result:

ok found '9.0000000000', expected '9.0000000000', error '0'

Test #24:

score: 0
Accepted
time: 20ms
memory: 47960kb

input:

10 95
85 89 36 9 18 3 13 23 11 36

output:

2.4793632463461177

result:

ok found '2.4793632463', expected '2.4793632463', error '0'

Test #25:

score: 0
Accepted
time: 50ms
memory: 55696kb

input:

12 94
1 80 8 83 8 10 5 6 10 12 84 2

output:

7.6435123358028063

result:

ok found '7.6435123358', expected '7.6435123358', error '0'

Test #26:

score: 0
Accepted
time: 62ms
memory: 53636kb

input:

12 93
81 83 1 1 1 1 1 1 1 1 78 1

output:

8.9999999997840019

result:

ok found '8.9999999998', expected '8.9999999998', error '7.10543e-15'

Test #27:

score: 0
Accepted
time: 124ms
memory: 89840kb

input:

13 92
5 85 5 76 2 3 5 1 3 74 80 2 2

output:

8.9971917217588383

result:

ok found '8.9971917218', expected '8.9971917218', error '1.77636e-15'

Test #28:

score: 0
Accepted
time: 701ms
memory: 133456kb

input:

15 91
82 12 8 72 12 6 4 7 3 9 9 78 91 75 90

output:

3.9003021787079568

result:

ok found '3.9003021787', expected '3.9003021787', error '1.33227e-15'

Test #29:

score: 0
Accepted
time: 517ms
memory: 129396kb

input:

15 90
1 85 7 77 14 5 87 88 7 78 82 7 11 73 79

output:

3.3564959736798172

result:

ok found '3.3564959737', expected '3.3564959737', error '0'

Test #30:

score: 0
Accepted
time: 16ms
memory: 79776kb

input:

11 85
1 1 1 1 20 4 1 11 55 4 1

output:

9.9968847363218917

result:

ok found '9.9968847363', expected '9.9968847363', error '3.55271e-15'

Test #31:

score: 0
Accepted
time: 46ms
memory: 82768kb

input:

12 80
5 2 3 2 1 6 2 23 5 1 24 16

output:

9.9328518197873753

result:

ok found '9.9328518198', expected '9.9328518198', error '1.77636e-15'

Test #32:

score: 0
Accepted
time: 159ms
memory: 72756kb

input:

14 50
14 5 1 10 1 5 2 1 16 6 2 2 7 3

output:

9.3514786296024875

result:

ok found '9.3514786296', expected '9.3514786296', error '1.77636e-15'

Test #33:

score: 0
Accepted
time: 458ms
memory: 134588kb

input:

15 93
9 1 18 1 2 6 7 13 30 3 1 1 2 1 1

output:

13.9449795968034890

result:

ok found '13.9449795968', expected '13.9449795968', error '5.32907e-15'

Test #34:

score: 0
Accepted
time: 454ms
memory: 141924kb

input:

15 100
2 5 1 26 9 1 7 34 6 2 20 5 72 3 7

output:

10.8193012536022539

result:

ok found '10.8193012536', expected '10.8193012536', error '3.55271e-15'

Test #35:

score: 0
Accepted
time: 488ms
memory: 143372kb

input:

15 100
1 8 15 22 29 36 43 50 57 64 71 78 85 92 99

output:

1.4160491639807899

result:

ok found '1.4160491640', expected '1.4160491640', error '6.66134e-16'

Test #36:

score: 0
Accepted
time: 568ms
memory: 142836kb

input:

15 100
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

output:

9.6287573442960967

result:

ok found '9.6287573443', expected '9.6287573443', error '1.77636e-15'

Test #37:

score: 0
Accepted
time: 948ms
memory: 138436kb

input:

15 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

output:

0.0000000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Extra Test:

score: 0
Extra Test Passed