QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817158#9300. So Many Possibilities...ucup-team902AC ✓120ms109000kbC++201.7kb2024-12-16 20:40:452024-12-16 20:40:51

Judging History

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

  • [2024-12-16 20:40:51]
  • 评测
  • 测评结果:AC
  • 用时:120ms
  • 内存:109000kb
  • [2024-12-16 20:40:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, m;
    cin >> n >> m;
    double ans = 0;
    vector<int> a(n);
    vector<vector<double>> dp(1 << n, vector<double>(200, 0)), coef(1 << n, vector<double>(200, 0));
    vector<vector<double>> c(200, vector<double>(200, 0));
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> sum(1 << n);
    for (int i = 0; i <= 199; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i < m; i++)
        dp[0][i] = dp[0][i - 1] / n;
    coef[0][0] = 1;
    for (int sta = 1; sta < (1 << n); sta++) {
        int low = sta & (-sta), p = __builtin_ctz(sta);
        int cnt = n - __builtin_popcount(sta);
        sum[sta] = sum[sta ^ low] + a[p];
        for (int i = 0; i < n; i++)
            if ((sta >> i) & 1)
                for (int j = sum[sta]; j <= m; j++)
                    dp[sta][j] += dp[sta ^ (1 << i)][j - 1] / (cnt + 1) * c[j - sum[sta ^ (1 << i)] - 1][a[i] - 1];
        for (int i = sum[sta] + 1; i <= m; i++)
            dp[sta][i] += dp[sta][i - 1] / cnt;
        for (int i = 0; i < a[p]; i++)
            for (int j = 0; i + j <= m; j++)
                coef[sta][i + j] += c[i + j][j] * coef[sta ^ low][j];
    }
    for (int sta = 1; sta < (1 << n); sta++)
        if (sum[sta] <= m)
            ans += __builtin_popcount(sta) * dp[sta][m] * coef[((1 << n) - 1) ^ sta][m - sum[sta]];
    cout << fixed << setprecision(12) << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
2 2

output:

0.500000000000

result:

ok found '0.5000000000', expected '0.5000000000', error '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4020kb

input:

3 3
1 2 3

output:

1.083333333333

result:

ok found '1.0833333333', expected '1.0833333333', error '3.33289e-13'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4192kb

input:

3 100
80 32 38

output:

0.917682017513

result:

ok found '0.9176820175', expected '0.9176820175', error '2.97318e-13'

Test #4:

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

input:

4 100
31 80 40 28

output:

0.389601136717

result:

ok found '0.3896011367', expected '0.3896011367', error '1.47604e-13'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4504kb

input:

8 100
37 42 41 43 52 24 7 21

output:

0.996650548013

result:

ok found '0.9966505480', expected '0.9966505480', error '1.22125e-14'

Test #6:

score: 0
Accepted
time: 2ms
memory: 5316kb

input:

9 100
6 13 4 6 20 13 10 25 25

output:

5.755547655021

result:

ok found '5.7555476550', expected '5.7555476550', error '2.66454e-14'

Test #7:

score: 0
Accepted
time: 2ms
memory: 6960kb

input:

10 10
6 5 6 10 9 6 10 7 1 9

output:

0.653713647886

result:

ok found '0.6537136479', expected '0.6537136479', error '2.56684e-13'

Test #8:

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

input:

15 50
6 5 9 1 3 3 10 19 16 18 10 12 16 14 6

output:

3.038971162172

result:

ok found '3.0389711622', expected '3.0389711622', error '8.43769e-14'

Test #9:

score: 0
Accepted
time: 108ms
memory: 108836kb

input:

15 100
80 42 42 99 93 31 22 48 37 58 77 96 5 87 79

output:

0.803948374562

result:

ok found '0.8039483746', expected '0.8039483746', error '3.99902e-13'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

3 50
34 30 36

output:

0.000100617103

result:

ok found '0.0001006171', expected '0.0001006171', error '4.148e-13'

Test #11:

score: 0
Accepted
time: 3ms
memory: 7044kb

input:

10 90
10 11 9 10 10 8 11 13 8 9

output:

6.382627579873

result:

ok found '6.3826275799', expected '6.3826275799', error '7.99361e-15'

Test #12:

score: 0
Accepted
time: 7ms
memory: 16832kb

input:

12 100
12 13 10 11 11 14 14 10 7 8 4 8

output:

5.784451171289

result:

ok found '5.7844511713', expected '5.7844511713', error '2.14051e-13'

Test #13:

score: 0
Accepted
time: 54ms
memory: 109000kb

input:

15 100
12 11 12 10 15 12 7 6 12 5 11 7 10 11 9

output:

3.850874013381

result:

ok found '3.8508740134', expected '3.8508740134', error '2.72227e-13'

Test #14:

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

input:

15 100
7 7 6 4 11 8 12 8 5 7 9 8 10 8 15

output:

7.813084239524

result:

ok found '7.8130842395', expected '7.8130842395', error '2.57572e-13'

Test #15:

score: 0
Accepted
time: 3ms
memory: 6992kb

input:

10 95
8 11 6 14 6 5 11 14 10 14

output:

8.138051491019

result:

ok found '8.1380514910', expected '8.1380514910', error '1.77636e-13'

Test #16:

score: 0
Accepted
time: 3ms
memory: 16780kb

input:

12 93
4 8 6 8 12 8 10 6 8 8 13 9

output:

9.120009675931

result:

ok found '9.1200096759', expected '9.1200096759', error '5.15143e-14'

Test #17:

score: 0
Accepted
time: 77ms
memory: 108816kb

input:

15 99
9 5 8 4 9 7 4 6 7 7 5 6 8 8 7

output:

14.000000000000

result:

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

Test #18:

score: 0
Accepted
time: 59ms
memory: 108996kb

input:

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

output:

15.000000000000

result:

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

Test #19:

score: 0
Accepted
time: 1ms
memory: 3992kb

input:

5 10
18 68 13 47 14

output:

0.000000000000

result:

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

Test #20:

score: 0
Accepted
time: 5ms
memory: 6960kb

input:

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

output:

0.000000000000

result:

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

Test #21:

score: 0
Accepted
time: 96ms
memory: 108884kb

input:

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

output:

0.000000000000

result:

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

Test #22:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

5 100
14 89 6 98 11

output:

2.999741338238

result:

ok found '2.9997413382', expected '2.9997413382', error '3.72147e-13'

Test #23:

score: 0
Accepted
time: 2ms
memory: 6940kb

input:

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

output:

9.000000000000

result:

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

Test #24:

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

input:

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

output:

2.479363246346

result:

ok found '2.4793632463', expected '2.4793632463', error '1.17684e-13'

Test #25:

score: 0
Accepted
time: 7ms
memory: 16880kb

input:

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

output:

7.643512335803

result:

ok found '7.6435123358', expected '7.6435123358', error '1.93623e-13'

Test #26:

score: 0
Accepted
time: 12ms
memory: 16804kb

input:

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

output:

8.999999999784

result:

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

Test #27:

score: 0
Accepted
time: 13ms
memory: 29908kb

input:

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

output:

8.997191721759

result:

ok found '8.9971917218', expected '8.9971917218', error '1.59872e-13'

Test #28:

score: 0
Accepted
time: 80ms
memory: 109000kb

input:

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

output:

3.900302178708

result:

ok found '3.9003021787', expected '3.9003021787', error '4.44089e-14'

Test #29:

score: 0
Accepted
time: 43ms
memory: 108920kb

input:

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

output:

3.356495973680

result:

ok found '3.3564959737', expected '3.3564959737', error '1.82965e-13'

Test #30:

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

input:

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

output:

9.996884736322

result:

ok found '9.9968847363', expected '9.9968847363', error '1.1191e-13'

Test #31:

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

input:

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

output:

9.932851819787

result:

ok found '9.9328518198', expected '9.9328518198', error '3.76588e-13'

Test #32:

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

input:

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

output:

9.351478629602

result:

ok found '9.3514786296', expected '9.3514786296', error '4.86722e-13'

Test #33:

score: 0
Accepted
time: 53ms
memory: 108848kb

input:

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

output:

13.944979596803

result:

ok found '13.9449795968', expected '13.9449795968', error '4.83169e-13'

Test #34:

score: 0
Accepted
time: 27ms
memory: 108916kb

input:

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

output:

10.819301253602

result:

ok found '10.8193012536', expected '10.8193012536', error '2.57572e-13'

Test #35:

score: 0
Accepted
time: 37ms
memory: 108836kb

input:

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

output:

1.416049163981

result:

ok found '1.4160491640', expected '1.4160491640', error '2.1072e-13'

Test #36:

score: 0
Accepted
time: 67ms
memory: 108800kb

input:

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

output:

9.628757344296

result:

ok found '9.6287573443', expected '9.6287573443', error '9.76996e-14'

Test #37:

score: 0
Accepted
time: 120ms
memory: 108832kb

input:

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

output:

0.000000000000

result:

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

Extra Test:

score: 0
Extra Test Passed