oj.uz

Submission #19017

# Submission time Handle Problem Language Result Execution time Memory
19017 2016-02-17T04:25:47 Z tncks0121 카드 (kriii4_Z) C++14
100 / 100
 7363 ms 1868 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
#include <iostream>
#include <unordered_map>
  
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
  
#define debug(format, ...) printf(format, __VA_ARGS__);
  
const ll MOD = (ll)1e9 + 7;
  
ll modpow (ll a, ll b) {
    a %= MOD;
    ll ret = 1;
    while(b > 0) {
        if(b & 1) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ret;
}
  
struct mint {
    ll val;
    mint(ll val = 0): val((val % MOD + MOD) % MOD) { }
    mint operator+(mint p) { return val + p.val; }
    mint operator-(mint p) { return val - p.val; }
    mint operator*(mint p) { return val * p.val; }
    mint operator/(mint p) { return val * modpow(p.val, MOD-2); }
};
  
int N, L;
  
const int N_ = 3050, L_ = 3050;
mint tb[L_], nxt[L_];
  
int D[N_];
int freq[N_];
  
mint invfac[L_], inv[L_], fac[L_];
  
int main() {
    assert(scanf("%d%d", &N, &L) == 2);
    assert(1 <= N && N <= 3000);
    assert(1 <= L && L <= 3000);
    for(int i = 1; i <= N; i++) {
        assert(scanf("%d", D+i) == 1);
        assert(0 <= D[i] && D[i] <= 10);
        ++freq[D[i]];
    }
  
    sort(D+1, D+N+1);
  
    inv[1] = 1;
    for(int i = 2; i < L_; i++) {
        inv[i] = inv[MOD % i] * -(MOD / i);
    }
  
    invfac[0] = fac[0] = 1;
    for(int i = 1; i <= L; i++) {
        fac[i] = fac[i-1] * i;
        invfac[i] = invfac[i-1] * inv[i];
    }
  
    tb[0] = 1;
    for(int d = 0; d <= 10; d++) if(freq[d] > 0) {
        vector<mint> base(L+1, 0);
        for(int j = d; j <= L; j++) base[j] = invfac[j];
  
        auto multiply = [](vector<mint> &p, vector<mint> &q) {
            for(int i = L; i >= 0; i--) {
                mint t = 0;
                for(int k = 0; k <= i; k++) t = t + p[i-k] * q[k];
                p[i] = t;
            }
        };
  
        vector<mint> coef, cur(L+1, 0);
        for(int j = d; j <= L; j++) cur[j] = invfac[j];
  
        for(int k = 0; (1<<k) <= freq[d]; k++) {
            if((freq[d] >> k) & 1) {
                if(coef.empty()) coef = cur;
                else multiply(coef, cur);
            }
            multiply(cur, cur);
        }
  
        for(int j = 0; j <= L; j++) {
            nxt[j] = 0;
            for(int k = 0; k <= j; k++)
                nxt[j] = nxt[j] + coef[j-k] * tb[k];
        }
  
        copy(nxt, nxt + L + 1, tb);
  
    }
  
    mint ans = tb[L] * fac[L] / modpow(N, L);
    printf("%lld\n", ans.val);
  
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1859 ms 1868 KB Output is correct
2 Correct 1945 ms 1868 KB Output is correct
3 Correct 1320 ms 1868 KB Output is correct
4 Correct 1928 ms 1868 KB Output is correct
5 Correct 1693 ms 1868 KB Output is correct
6 Correct 1506 ms 1868 KB Output is correct
7 Correct 1675 ms 1868 KB Output is correct
8 Correct 1665 ms 1868 KB Output is correct
9 Correct 1754 ms 1868 KB Output is correct
10 Correct 1483 ms 1868 KB Output is correct
11 Correct 1719 ms 1868 KB Output is correct
12 Correct 1449 ms 1868 KB Output is correct
13 Correct 1705 ms 1868 KB Output is correct
14 Correct 2104 ms 1868 KB Output is correct
15 Correct 1707 ms 1868 KB Output is correct
16 Correct 1541 ms 1868 KB Output is correct
17 Correct 2112 ms 1868 KB Output is correct
18 Correct 1679 ms 1868 KB Output is correct
19 Correct 1785 ms 1868 KB Output is correct
20 Correct 1778 ms 1868 KB Output is correct
21 Correct 1447 ms 1868 KB Output is correct
22 Correct 1510 ms 1868 KB Output is correct
23 Correct 1198 ms 1868 KB Output is correct
24 Correct 1449 ms 1868 KB Output is correct
25 Correct 1573 ms 1868 KB Output is correct

Subtask #2
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 2552 ms 1868 KB Output is correct
2 Correct 2463 ms 1868 KB Output is correct
3 Correct 4858 ms 1868 KB Output is correct
4 Correct 5994 ms 1868 KB Output is correct
5 Correct 3772 ms 1868 KB Output is correct
6 Correct 6090 ms 1868 KB Output is correct
7 Correct 5934 ms 1868 KB Output is correct
8 Correct 6002 ms 1868 KB Output is correct
9 Correct 851 ms 1868 KB Output is correct
10 Correct 2043 ms 1868 KB Output is correct
11 Correct 2145 ms 1868 KB Output is correct
12 Correct 2889 ms 1868 KB Output is correct
13 Correct 3396 ms 1868 KB Output is correct
14 Correct 2972 ms 1868 KB Output is correct
15 Correct 3531 ms 1868 KB Output is correct
16 Correct 2435 ms 1868 KB Output is correct
17 Correct 2011 ms 1868 KB Output is correct
18 Correct 6641 ms 1868 KB Output is correct
19 Correct 6178 ms 1868 KB Output is correct
20 Correct 7363 ms 1868 KB Output is correct