QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
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: 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:
0
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:
0
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:
0
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:
0
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:
0
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'