QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#350941	#7063. Space Station	Rong7	WA	576ms	29396kb	C++14	2.7kb	2024-03-11 10:22:02	2024-03-11 10:22:02

Judging History

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

[2024-03-11 10:22:02]
评测

测评结果：WA
用时：576ms
内存：29396kb

查看

[2024-03-11 10:22:02]
提交

answer

// Not afraid to dark.

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

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
    int llen;
    inline int get_string (char c[], int &len = llen){
        len = 0;
        read_char = getchar ();
        while (read_char == ' ' || read_char == '\n' || read_char == '\r')
            read_char = getchar ();
        while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
            c[++ len] = read_char;
            read_char = getchar ();
        }
        return len;
    }
}

const int N = 1e5, V = 50, mod = 1e9 + 7;
const unsigned long long sed = 47;
int n, ia, ct[V + 5], ans, jc[N + 5], inv[N + 5], inj[N + 5], sum;

vector < int > ac;
unordered_map < unsigned long long , int > mp;

inline unsigned long long Upload (vector < int > &a){
    unsigned long long res = 0;
    for (int i = V;i >= 1;-- i)
        res = res * sed + a[i];
    return res;
}

inline int Solve (int rest, int sum){
    if (rest == 0)
        return 1;
    if (sum >= V)
        return jc[rest];
    unsigned long long Hash = Upload (ac);
    if (mp.count (Hash))
        return mp[Hash];
    for (int i = 1;i <= sum;++ i)
        if (ac[i] < ct[i]){
            ++ ac[i];
            mp[Hash] += Solve (rest - 1, sum + i) * (ct[i] - ac[i] + 1) % mod;
            -- ac[i];
        }
    mp[Hash] %= mod;
    return mp[Hash];
}

signed main (){
    io::read (n), io::read (ia);
    sum += ia;
    for (int i = 1, a;i <= n;++ i){
        ++ ct[io::read (a)];
        sum += a;
    }
    inv[1] = jc[0] = jc[1] = inj[0] = inj[1] = 1;
    for (int i = 2;i <= n;++ i){
        inv[i] = 1ll * inv[i - mod % i] * (mod / i + 1) % mod;
        inj[i] = 1ll * inj[i - 1] * inv[i] % mod;
        jc[i] = 1ll * jc[i - 1] * i % mod;
    }
    ac.resize (V + 1, 0);
    io::write (1ll * Solve (n - ct[0], ia) * jc[n] % mod * inj[n - ct[0]] % mod), puts ("");
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3808kb

input:

3
2 1 2 3

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3744kb

input:

5
1 1 1 1 2 3

output:

result:

ok single line: '54'

Test #3:

score: 0

Accepted

time: 3ms

memory: 5920kb

input:

100000
47 25 43 22 17 6 15 17 45 4 14 34 46 22 0 8 2 48 41 6 49 42 21 25 48 43 2 17 27 25 38 31 39 48 13 49 24 30 36 19 29 47 48 1 4 5 12 9 21 39 30 21 8 4 9 45 18 0 3 29 26 18 24 39 31 49 22 4 46 21 27 11 11 7 8 3 26 25 29 4 1 21 34 4 44 39 13 26 33 44 5 17 10 32 37 25 44 34 17 14 40 32 27 39 41 6 ...

output:

268605493

result:

ok single line: '268605493'

Test #4:

score: 0

Accepted

time: 3ms

memory: 5872kb

input:

100000
35 39 20 34 18 5 21 21 45 38 48 44 50 42 35 23 21 18 24 9 40 18 16 20 41 27 25 4 0 5 9 7 39 26 47 13 18 27 43 45 31 20 45 39 7 29 4 41 6 39 4 27 7 24 42 10 49 21 9 21 33 12 7 2 24 13 47 11 43 25 8 18 5 14 44 9 14 50 50 19 6 18 45 41 0 27 20 44 17 19 5 26 38 19 1 30 10 32 46 4 24 27 28 32 27 3...

output:

590621358

result:

ok single line: '590621358'

Test #5:

score: 0

Accepted

time: 11ms

memory: 6692kb

input:

100000
21 4 24 20 20 30 50 25 47 22 31 30 2 37 43 13 16 12 8 39 31 18 10 42 32 10 49 17 46 35 5 36 13 4 32 4 12 22 49 44 6 18 40 24 34 4 48 22 15 10 1 31 30 44 49 24 29 16 39 11 13 31 42 39 17 28 20 18 15 30 40 23 49 45 3 15 2 24 21 34 11 15 5 2 7 17 27 11 2 44 31 38 16 32 17 9 2 30 49 18 35 46 30 5...

output:

983292446

result:

ok single line: '983292446'

Test #6:

score: 0

Accepted

time: 255ms

memory: 17568kb

input:

100000
7 20 29 6 48 4 29 30 48 7 16 15 7 7 26 28 38 32 42 43 47 19 4 37 25 21 21 3 43 13 2 38 14 34 40 19 7 18 5 43 33 16 36 11 35 30 15 2 25 10 49 9 2 40 31 40 9 36 19 28 19 23 26 27 10 18 45 24 38 35 48 6 42 27 13 22 16 50 17 25 42 10 16 15 41 30 6 31 36 17 31 49 18 18 33 14 19 5 27 7 19 15 32 43 ...

output:

363626098

result:

ok single line: '363626098'

Test #7:

score: 0

Accepted

time: 2ms

memory: 6116kb

input:

100000
46 11 7 43 50 4 34 33 49 42 49 0 11 1 34 42 33 26 26 22 39 46 24 33 18 5 44 16 15 42 23 14 14 11 23 10 27 15 11 18 35 39 6 48 12 4 8 34 34 34 48 14 0 9 11 3 41 6 25 19 50 17 9 12 27 33 44 31 36 14 29 12 9 9 23 27 4 0 39 39 46 32 27 29 48 19 13 48 20 41 32 34 47 5 23 17 37 4 29 48 4 35 34 10 3...

output:

545614387

result:

ok single line: '545614387'

Test #8:

score: 0

Accepted

time: 3ms

memory: 6152kb

input:

100000
33 26 12 4 27 29 13 37 50 26 33 35 14 21 17 6 4 22 9 50 30 47 19 28 10 40 16 30 11 21 20 17 12 40 6 24 22 35 18 16 10 38 2 34 40 4 0 14 43 32 45 18 22 3 44 18 46 27 5 9 4 35 44 50 20 50 17 38 8 17 11 18 2 14 7 33 46 25 10 3 1 28 12 41 4 8 21 17 30 15 32 44 25 44 38 48 29 2 6 11 14 4 35 2 42 4...

output:

93496998

result:

ok single line: '93496998'

Test #9:

score: 0

Accepted

time: 15ms

memory: 6668kb

input:

100000
20 41 41 40 28 3 16 41 1 11 41 47 19 16 0 21 23 41 43 3 46 47 13 48 28 48 40 16 33 0 16 44 38 18 41 15 16 32 24 17 12 35 49 20 42 28 44 46 28 5 43 48 22 25 26 9 25 48 35 27 35 28 27 37 13 15 42 46 5 22 17 25 46 47 18 40 34 0 5 44 30 23 23 3 37 23 2 35 14 15 32 4 2 30 2 2 46 2 35 2 49 0 37 21 ...

output:

558286380

result:

ok single line: '558286380'

Test #10:

score: 0

Accepted

time: 342ms

memory: 24616kb

input:

100000
6 6 45 27 30 1 47 45 1 45 25 31 50 37 8 10 19 36 28 33 37 23 8 45 21 33 12 29 30 29 36 47 38 47 50 4 10 27 31 42 38 8 44 31 19 3 37 27 37 4 14 2 44 19 7 23 6 17 40 18 41 46 12 50 6 4 41 26 28 27 50 31 39 29 27 45 22 25 27 9 36 21 34 14 45 11 9 2 50 39 32 15 4 17 17 30 12 0 38 16 35 19 39 13 3...

output:

294711323

result:

ok single line: '294711323'

Test #11:

score: 0

Accepted

time: 3ms

memory: 5908kb

input:

100000
45 22 24 14 7 26 0 48 1 30 9 17 2 32 43 25 40 5 11 11 29 23 28 40 13 17 36 43 2 33 32 23 37 24 33 21 5 23 36 40 40 6 14 17 47 28 29 7 47 27 13 6 16 40 39 38 37 38 21 7 22 40 47 36 24 19 15 33 0 32 31 38 32 10 37 0 36 50 49 50 41 42 46 27 27 26 15 21 34 12 32 25 31 5 32 35 5 50 16 5 46 39 15 3...

output:

523779527

result:

ok single line: '523779527'

Test #12:

score: 0

Accepted

time: 3ms

memory: 5904kb

input:

100000
35 17 27 31 8 22 13 24 9 5 26 31 40 34 8 29 11 19 8 33 49 15 45 38 32 21 11 3 14 29 6 13 5 31 39 42 26 49 37 43 7 17 1 11 26 5 27 23 23 4 34 31 39 14 48 7 30 19 45 3 5 4 0 15 50 23 20 11 11 2 43 33 39 19 45 10 2 34 48 1 19 12 14 42 15 39 1 8 44 45 9 13 29 26 22 4 17 43 32 29 14 31 8 0 40 5 5 ...

output:

845953523

result:

ok single line: '845953523'

Test #13:

score: 0

Accepted

time: 2ms

memory: 6136kb

input:

100000
8 3 1 5 0 0 3 1 5 10 39 44 42 39 38 40 42 47 47 37 42 43 43 42 50 38 41 44 45 43 38 49 45 39 46 40 38 50 48 40 50 45 44 38 42 45 41 44 50 46 39 37 37 43 42 50 46 40 45 38 50 47 42 46 50 41 38 46 44 38 46 38 47 47 38 40 42 50 49 41 42 45 48 49 38 50 40 44 45 43 44 40 46 50 40 50 50 44 43 41 44...

output:

result:

ok single line: '0'

Test #14:

score: 0

Accepted

time: 0ms

memory: 5864kb

input:

100000
10 4 0 5 4 0 8 8 1 1 43 46 46 47 50 48 49 49 43 49 42 42 47 50 48 43 42 45 42 44 48 43 47 47 49 43 48 44 42 47 46 43 49 49 49 44 44 48 46 46 48 45 49 48 50 45 50 43 50 50 50 43 45 48 42 46 47 42 49 48 48 43 50 43 50 47 49 42 50 49 48 48 43 50 47 48 49 42 42 45 46 49 45 45 47 44 44 45 47 45 50...

output:

result:

ok single line: '0'

Test #15:

score: 0

Accepted

time: 2ms

memory: 5884kb

input:

100000
1 10 9 6 6 0 9 8 0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...

output:

result:

ok single line: '0'

Test #16:

score: 0

Accepted

time: 3ms

memory: 6072kb

input:

100000
10 7 7 0 3 7 0 8 0 5 48 48 49 49 50 48 48 50 48 49 50 49 49 48 48 48 49 48 48 48 50 49 48 48 48 48 50 49 49 49 48 50 49 48 49 49 50 50 49 50 50 48 50 49 48 50 49 48 50 48 50 48 49 49 48 49 49 50 50 48 48 50 50 48 50 49 48 50 49 50 49 48 48 50 49 48 49 49 50 49 50 48 48 49 49 48 49 50 50 49 48...

output:

result:

ok single line: '0'

Test #17:

score: 0

Accepted

time: 0ms

memory: 5952kb

input:

100000
5 9 5 0 8 7 9 45 45 46 49 45 47 46 45 45 47 46 46 44 46 47 49 48 47 48 45 46 49 45 44 47 44 45 48 45 45 46 50 48 46 48 45 47 50 50 46 48 47 50 47 44 44 44 46 44 48 49 50 44 47 49 49 50 45 49 49 45 45 48 47 46 47 44 49 50 50 48 50 50 50 45 50 48 45 48 50 50 49 47 50 47 49 49 47 49 45 45 47 50 ...

output:

result:

ok single line: '0'

Test #18:

score: -100

Wrong Answer

time: 576ms

memory: 29396kb

input:

100000
1 25 50 6 21 4 25 36 20 32 10 14 44 0 19 1 38 41 5 25 38 11 20 11 37 5 4 19 39 11 45 16 38 14 44 20 38 25 32 5 34 37 28 4 41 4 12 34 31 32 11 18 33 10 6 16 29 40 24 14 9 17 16 42 26 16 24 4 46 34 20 24 27 21 27 17 17 7 8 50 0 36 30 4 5 16 43 0 19 29 25 11 16 0 50 30 12 50 26 9 0 46 38 11 50 4...

output:

521183323

result:

wrong answer 1st lines differ - expected: '646807826', found: '521183323'