QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98953#5105. Hand of the Free MarkeduphargaurTL 3ms3668kbC++201.2kb2023-04-21 01:58:422023-04-21 01:58:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-21 01:58:46]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:3668kb
  • [2023-04-21 01:58:42]
  • 提交

answer

#include <iostream>
using namespace std;

int k, m, n, a[99], b[99];
long double ans, totnum, num, p;


long double fact(long double n);
 
long double nCr(long double n, long double r)
{
    return fact(n) / (fact(r) * fact(n - r));
}
 
// Returns factorial of n
long double fact(long double n)
{
      if(n==0)
      return 1;
    long double res = 1;
    for (long double i = 2; i <= n; i++)
        res = res * i;
    return res;
}

void dfs(int nw, int sm) {
    if (nw > m) {
        if (sm ^ k)
            return;
        num = 1;
        p = 0;
        for (int i = 1; i <= m; ++i)
            num *= nCr(a[i], b[i]), p += (long double)b[i] / (a[i] - b[i] + 1);
        for (int i = 1; i < k; ++i)
            p *= i;
        if (p > 1)
            ans += num / totnum;
        else
            ans += num / totnum * p;
        return;
    }
    for (int i = 0; i + sm <= k && i <= a[nw]; ++i)
        b[nw] = i, dfs(nw + 1, sm + i);
}

int main() {
    cin >> k >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i], n += a[i];
    totnum = nCr(n, k);
    dfs(1, 0);
    cout.precision(10);
    cout << fixed << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3480kb

input:

3 3 2 1 2

output:

1.0000000000

result:

ok answer is 1.0000000000

Test #2:

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

input:

3 4 1 3 1 15

output:

0.7719298246

result:

ok answer is 0.7719298246

Test #3:

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

input:

4 1 27

output:

1.0000000000

result:

ok answer is 1.0000000000

Test #4:

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

input:

4 3 1 2 28

output:

0.9739710790

result:

ok answer is 0.9739710790

Test #5:

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

input:

4 3 1 3 28

output:

0.9772246941

result:

ok answer is 0.9772246941

Test #6:

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

input:

5 1 130

output:

0.9523809524

result:

ok answer is 0.9523809524

Test #7:

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

input:

5 3 2 16 200

output:

0.7490392123

result:

ok answer is 0.7490392123

Test #8:

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

input:

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

output:

0.6954998646

result:

ok answer is 0.6954998646

Test #9:

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

input:

4 10 1 20 3 4 1 2 40 4 5 500

output:

0.2435721816

result:

ok answer is 0.2435721816

Test #10:

score: -100
Time Limit Exceeded

input:

3 2 152333146 373955979

output:


result: