QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791280#9300. So Many Possibilities...IllusionaryDominance#TL 886ms75400kbC++141.9kb2024-11-28 17:50:342024-11-28 17:50:42

Judging History

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

  • [2024-11-28 17:50:42]
  • 评测
  • 测评结果:TL
  • 用时:886ms
  • 内存:75400kb
  • [2024-11-28 17:50:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
using ll = long long;
using db = __float128;

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];
    }
    long double Ans = (long double)ans;
    cout << fixed << setprecision(16) << Ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8084kb

input:

2 2
2 2

output:

0.5000000000000000

result:

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

Test #2:

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

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

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

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: 34ms
memory: 40132kb

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: 24ms
memory: 59288kb

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: 6ms
memory: 16504kb

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: 886ms
memory: 75400kb

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: -100
Time Limit Exceeded

input:

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

output:


result: