QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#864804#5646. Uniform ChemistryjuancsAC ✓2ms7040kbC++202.0kb2025-01-21 08:40:122025-01-21 08:40:12

Judging History

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

  • [2025-01-21 08:40:12]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:7040kb
  • [2025-01-21 08:40:12]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;

typedef long long ll;
typedef vector<int>vi;
typedef pair<int, int> ii;
typedef tree<int,null_type,less<int>, rb_tree_tag, 
    tree_order_statistics_node_update> ordered_set;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;

#define el '\n'
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define forn(i,n) for(int i = 0; i < n;++i)
#define for1(i, n) for(int i = 1; i <= n; ++i)
#define fore(i, l, r) for(int i = l; i <= r; ++i)
#define fored(i, l, r) for(int i = r; i >= l; --i)
#define pb push_back
#define db(x) cerr << #x << ' ' << x << el

void solve(){
    int n, m;
    cin >> n >> m;
    vi a(m);
    forn(i, m){
        cin >> a[i];
    }
    vvvld dp(m, vvld(n+1, vld(n + 1)));
    forn(i, m){
        dp[i][0][a[i]] = 1;
    }
    int cy = 1;
    while(cy <= n){
        forn(i, m){
            fore(j, a[i], n){
                fore(k, j + 1, n){
                    dp[i][cy][k] += dp[i][cy - 1][j]*(1.0L/ld(n - j));
                }
            }
            ++a[i];
        }
        ++cy;
    }
    vld ans(m);
    vvvld suf = dp;
    
    forn(i, m){
        fored(yr, 1, n - 1){
            suf[i][yr][n] += suf[i][yr + 1][n];
        }
    }

    // forn(yr, n){
    //     for1(i, n){
    //         cout << dp[0][yr][i] << ' ';
    //     }
    //     cout << el;
    // }

    fore(yr, 1, n){
        forn(i, m){
            ld ys = 1;
            forn(j, m){
                if(i == j)continue;
                ys *= suf[j][yr][n];
            }
            ans[i] += ys*dp[i][yr][n];
        }
    }
    forn(i, m)cout << ans[i] << ' ';
    cout << el;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.precision(20);
    int tt = 1;
    // cin>>tt;
    while(tt--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
1 1 1

output:

1 1 1 

result:

ok 3 numbers, max absolute error 0

Test #2:

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

input:

3 3
1 1 2

output:

0.5 0.5 1 

result:

ok 3 numbers, max absolute error 0

Test #3:

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

input:

3 3
1 1 1

output:

0.625 0.625 0.625 

result:

ok 3 numbers, max absolute error 0

Test #4:

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

input:

100 7
1 2 4 8 16 32 64

output:

0.17859346862375033462 0.17981045473107379641 0.18230677063927824725 0.18756536558781155884 0.19930042952939319789 0.22935632241384935477 0.34872251794410225528 

result:

ok 7 numbers, max absolute error 4.70606804e-10

Test #5:

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

input:

100 10
28 58 38 53 1 19 66 60 68 31

output:

0.13203124473441064699 0.1954783754445706473 0.14727832600343695871 0.18016945052977996734 0.10449528336206387847 0.12111203297217177253 0.22774417556729385906 0.20250682431319990349 0.2379248932513687138 0.13620726884859008364 

result:

ok 10 numbers, max absolute error 1.11022302e-16

Test #6:

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

input:

100 10
86 50 88 42 88 20 29 83 89 34

output:

0.2633535451163393681 0.096016845557971749518 0.29734628468613810335 0.085266761166790677512 0.29734628468613810335 0.06586164758713535996 0.072497069565826002231 0.22598103884075662425 0.31842780574297111583 0.076875608528127990423 

result:

ok 10 numbers, max absolute error 1.66533454e-16

Test #7:

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

input:

2 1
1

output:

1 

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #8:

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

input:

10 3
4 6 7

output:

0.37213541666666666668 0.52349537037037037045 0.66784336419753086422 

result:

ok 3 numbers, max absolute error 1.11022302e-16

Test #9:

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

input:

20 10
6 6 9 3 14 15 13 8 6 11

output:

0.15191773720888006943 0.15191773720888006943 0.18714646918867133753 0.12842754310202011704 0.31623420335559153965 0.37043457030763186861 0.27669775335329040053 0.17358207630566267411 0.15191773720888006943 0.2226133626771252282 

result:

ok 10 numbers, max absolute error 1.11022302e-16

Test #10:

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

input:

99 2
40 55

output:

0.53661402494642751303 0.62959269381274074939 

result:

ok 2 numbers, max absolute error 5.55111512e-16

Test #11:

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

input:

99 9
86 68 85 83 75 70 71 73 70

output:

0.29457411708976180759 0.14923449022955953114 0.27802947617845735035 0.25051406574653363641 0.18243542993531475792 0.15726387538773390457 0.1616578500370203191 0.17133817158708363 0.15726387538773390457 

result:

ok 9 numbers, max absolute error 1.66533454e-16