QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#350944#7063. Space StationRong7AC ✓638ms31828kbC++142.7kb2024-03-11 10:23:242024-03-11 10:23:24

Judging History

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

  • [2024-03-11 10:23:24]
  • 评测
  • 测评结果：AC
  • 用时：638ms
  • 内存：31828kb
查看
  • [2024-03-11 10:23:24]
  • 提交

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 = 57;
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

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

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

input:

3
2 1 2 3

output:

4

result:

ok single line: '4'

Test #2:

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

input:

5
1 1 1 1 2 3

output:

54

result:

ok single line: '54'

Test #3:

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

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: 5936kb

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: 6728kb

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: 246ms
memory: 17564kb

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: 0ms
memory: 6136kb

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: 5984kb

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: 14ms
memory: 6528kb

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: 317ms
memory: 24780kb

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: 2ms
memory: 6144kb

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: 5868kb

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: 0ms
memory: 5904kb

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:

0

result:

ok single line: '0'

Test #14:

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

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:

0

result:

ok single line: '0'

Test #15:

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

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:

0

result:

ok single line: '0'

Test #16:

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

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:

0

result:

ok single line: '0'

Test #17:

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

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:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 634ms
memory: 31828kb

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:

646807826

result:

ok single line: '646807826'

Test #19:

score: 0
Accepted
time: 638ms
memory: 31816kb

input:

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

output:

314526688

result:

ok single line: '314526688'

Test #20:

score: 0
Accepted
time: 564ms
memory: 29440kb

input:

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

output:

852903575

result:

ok single line: '852903575'

Test #21:

score: 0
Accepted
time: 493ms
memory: 26880kb

input:

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

output:

67686831

result:

ok single line: '67686831'

Test #22:

score: 0
Accepted
time: 431ms
memory: 24652kb

input:

100000
5 48 35 6 33 23 33 24 13 36 42 39 31 36 21 13 24 26 27 25 0 29 11 15 0 11 50 46 41 38 15 50 23 49 39 45 23 31 9 8 30 5 14 30 15 7 37 45 50 20 34 34 48 8 44 7 29 0 42 6 34 34 9 48 44 40 36 5 42 35 36 26 47 27 29 24 37 36 7 30 20 13 40 22 49 16 30 20 22 6 11 26 12 16 15 20 4 31 47 48 13 9 1 9 3...

output:

283449875

result:

ok single line: '283449875'

Test #23:

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

input:

94347
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

371131493

result:

ok single line: '371131493'

Test #24:

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

input:

1
1 0

output:

1

result:

ok single line: '1'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 20:34:04 | 開源專案