oj.uz

Submission #18988

# Submission time Handle Problem Language Result Execution time Memory
18988 2016-02-17T02:18:38 Z tncks0121 카드 (kriii4_Z) C++14
13 / 100
 3000 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 1855 ms 1868 KB Output is correct
2 Correct 1947 ms 1868 KB Output is correct
3 Correct 1318 ms 1868 KB Output is correct
4 Correct 1927 ms 1868 KB Output is correct
5 Correct 1693 ms 1868 KB Output is correct
6 Correct 1505 ms 1868 KB Output is correct
7 Correct 1676 ms 1868 KB Output is correct
8 Correct 1664 ms 1868 KB Output is correct
9 Correct 1751 ms 1868 KB Output is correct
10 Correct 1479 ms 1868 KB Output is correct
11 Correct 1716 ms 1868 KB Output is correct
12 Correct 1450 ms 1868 KB Output is correct
13 Correct 1701 ms 1868 KB Output is correct
14 Correct 2101 ms 1868 KB Output is correct
15 Correct 1706 ms 1868 KB Output is correct
16 Correct 1545 ms 1868 KB Output is correct
17 Correct 2112 ms 1868 KB Output is correct
18 Correct 1674 ms 1868 KB Output is correct
19 Correct 1791 ms 1868 KB Output is correct
20 Correct 1777 ms 1868 KB Output is correct
21 Correct 1448 ms 1868 KB Output is correct
22 Correct 1511 ms 1868 KB Output is correct
23 Correct 1198 ms 1868 KB Output is correct
24 Correct 1451 ms 1868 KB Output is correct
25 Correct 1570 ms 1868 KB Output is correct

Subtask #2
0.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 2551 ms 1868 KB Output is correct
2 Correct 2467 ms 1868 KB Output is correct
3 Execution timed out 3000 ms 1864 KB Program timed out
4 Halted 0 ms 0 KB -