QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #828632 | #1277. Permutation | yuanruiqi | AC ✓ | 1234ms | 47380kb | C++14 | 1.0kb | 2024-12-23 19:02:39 | 2024-12-23 19:02:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000000 + 7;
constexpr int maxn = 50 + 5;
int a[maxn];
int v[maxn];
void solve()
{
int n, m = 0;
cin >> n;
for (int i=1;i<=n;++i) cin >> a[i], ++v[a[i]];
unordered_map<i64, i64> f, g;
f.reserve(1000000);
g.reserve(1000000);
f[0] = 1;
i64 fac = 1;
for (int i=1;i<=n;++i)
{
if (!a[i]) fac = fac * ++m % mod;
swap(f, g);
f.clear();
for (auto [s, x] : g)
for (int j=1;j<=n;++j)
if ((~s >> j & 1) && (!a[i] || j == a[i]))
{
int o = 1;
for (int k=1;k<j&&j+k<=n&&o;++k)
if ((s >> j - k & 1) + (s >> j + k & 1) == 1) o = 0;
if (o) (f[s | (1ll << j)] += x) %= mod;
}
}
cout << (fac - f[(1ll << n + 1) - 2] + mod) % mod << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 19828kb
input:
2 3 0 0 0 7 1 0 3 0 0 6 0
output:
2 21
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 72ms
memory: 19832kb
input:
50 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
output:
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
result:
ok 50 tokens
Test #3:
score: 0
Accepted
time: 44ms
memory: 19912kb
input:
25 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0
output:
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
result:
ok 25 tokens
Test #4:
score: 0
Accepted
time: 54ms
memory: 19772kb
input:
16 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0 3 0 0 0
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
result:
ok 16 tokens
Test #5:
score: 0
Accepted
time: 23ms
memory: 20032kb
input:
5 10 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0
output:
3627734 3627734 3627734 3627734 3627734
result:
ok 5 tokens
Test #6:
score: 0
Accepted
time: 15ms
memory: 20260kb
input:
4 11 0 10 11 6 1 0 8 0 0 3 5 11 0 0 0 10 8 5 4 1 0 2 9 11 0 4 0 3 11 0 0 0 7 8 1 11 0 8 0 3 9 0 0 0 7 4 0
output:
24 24 120 720
result:
ok 4 tokens
Test #7:
score: 0
Accepted
time: 16ms
memory: 20104kb
input:
4 12 0 0 11 0 0 6 1 0 4 0 5 8 12 7 0 10 11 4 6 1 8 0 12 0 0 12 0 12 0 0 0 0 5 0 1 0 10 11 12 0 0 4 3 9 12 2 5 1 10 6 0
output:
720 24 5040 6
result:
ok 4 tokens
Test #8:
score: 0
Accepted
time: 20ms
memory: 20116kb
input:
3 13 0 13 6 3 0 11 0 0 0 0 1 2 0 13 9 0 0 0 0 0 8 0 5 7 0 12 0 13 0 0 0 0 0 0 3 10 2 9 0 12 0
output:
5040 40320 40320
result:
ok 3 tokens
Test #9:
score: 0
Accepted
time: 16ms
memory: 20124kb
input:
3 14 0 12 10 9 0 0 11 0 0 1 6 4 8 13 14 0 0 8 0 0 9 14 3 0 0 6 2 0 0 14 13 0 8 0 0 0 0 0 14 7 4 6 0 3
output:
120 40320 5040
result:
ok 3 tokens
Test #10:
score: 0
Accepted
time: 19ms
memory: 20412kb
input:
3 15 8 7 12 14 6 0 0 9 4 0 1 0 0 0 2 15 5 0 0 9 0 7 15 0 13 4 11 0 0 0 2 15 0 0 0 2 0 0 7 0 0 8 0 13 14 10 3
output:
720 5040 40320
result:
ok 3 tokens
Test #11:
score: 0
Accepted
time: 16ms
memory: 19828kb
input:
2 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
143388927 143388927
result:
ok 2 tokens
Test #12:
score: 0
Accepted
time: 11ms
memory: 19828kb
input:
1 30 21 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:
586750519
result:
ok "586750519"
Test #13:
score: 0
Accepted
time: 13ms
memory: 20120kb
input:
1 40 0 0 0 0 23 26 0 0 0 0 0 0 32 20 33 0 0 0 0 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0
output:
943272305
result:
ok "943272305"
Test #14:
score: 0
Accepted
time: 132ms
memory: 27172kb
input:
1 41 0 0 0 0 0 0 0 0 0 14 38 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 35 9 0 0
output:
523095984
result:
ok "523095984"
Test #15:
score: 0
Accepted
time: 223ms
memory: 28344kb
input:
1 42 0 0 0 0 0 0 0 0 0 0 0 0 4 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 38 0 0 0 1 0
output:
472948359
result:
ok "472948359"
Test #16:
score: 0
Accepted
time: 18ms
memory: 20040kb
input:
5 10 0 0 7 0 0 0 0 0 0 3 10 0 5 0 0 0 0 0 9 0 0 10 1 6 0 0 0 0 0 5 0 0 10 0 0 4 0 0 0 3 0 1 9 10 0 0 0 0 0 0 0 6 0 0
output:
40320 40320 5040 718 362648
result:
ok 5 tokens
Test #17:
score: 0
Accepted
time: 22ms
memory: 20336kb
input:
5 9 0 6 0 0 0 0 0 0 0 9 6 0 0 0 3 0 0 7 0 9 8 0 0 0 0 0 7 3 4 9 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 8 2 0
output:
40270 720 120 362384 4996
result:
ok 5 tokens
Test #18:
score: 0
Accepted
time: 275ms
memory: 28296kb
input:
1 42 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:
94131117
result:
ok "94131117"
Test #19:
score: 0
Accepted
time: 181ms
memory: 25896kb
input:
1 40 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:
614960773
result:
ok "614960773"
Test #20:
score: 0
Accepted
time: 71ms
memory: 22176kb
input:
1 35 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:
478043548
result:
ok "478043548"
Test #21:
score: 0
Accepted
time: 30ms
memory: 20564kb
input:
1 30 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:
343955582
result:
ok "343955582"
Test #22:
score: 0
Accepted
time: 15ms
memory: 20060kb
input:
1 25 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:
242322220
result:
ok "242322220"
Test #23:
score: 0
Accepted
time: 11ms
memory: 19920kb
input:
1 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
143388927
result:
ok "143388927"
Test #24:
score: 0
Accepted
time: 19ms
memory: 19788kb
input:
5 10 0 0 0 2 0 9 0 5 0 0 10 0 1 0 3 7 0 0 0 0 0 10 0 0 10 8 0 0 0 9 0 7 10 0 7 1 9 0 0 0 0 0 0 10 0 4 0 0 10 0 0 0 9 0
output:
5028 5000 719 5018 5034
result:
ok 5 tokens
Test #25:
score: 0
Accepted
time: 15ms
memory: 20116kb
input:
5 10 5 1 9 7 3 0 4 10 2 6 10 5 9 1 3 7 6 2 0 4 8 10 6 2 10 4 8 1 9 5 3 0 10 0 10 6 4 8 5 9 1 7 3 10 8 4 10 2 6 5 9 1 0 3
output:
0 0 0 0 0
result:
ok 5 tokens
Test #26:
score: 0
Accepted
time: 28ms
memory: 19912kb
input:
5 10 0 3 0 0 5 10 2 6 4 8 10 5 1 0 3 7 0 4 2 10 6 10 0 3 9 1 5 6 0 10 0 4 10 0 3 5 9 1 6 10 0 8 4 10 5 1 9 7 3 0 4 6 2 0
output:
4 1 5 1 1
result:
ok 5 tokens
Test #27:
score: 0
Accepted
time: 12ms
memory: 19536kb
input:
1 42 29 13 21 37 5 17 33 1 0 0 41 11 27 35 3 19 31 15 23 39 7 12 28 4 36 20 24 0 0 32 16 2 34 18 26 10 42 0 30 6 38 22
output:
118
result:
ok "118"
Test #28:
score: 0
Accepted
time: 13ms
memory: 19532kb
input:
1 42 37 5 21 13 29 17 1 33 25 9 41 3 35 0 0 27 23 0 7 31 15 32 16 8 40 24 0 0 20 28 0 30 0 0 38 22 10 0 0 0 0 18
output:
479001592
result:
ok "479001592"
Test #29:
score: 0
Accepted
time: 16ms
memory: 19780kb
input:
1 42 0 29 0 0 21 33 1 17 41 9 0 15 31 0 7 23 0 0 0 0 35 20 4 36 28 12 32 0 0 40 24 26 10 0 18 34 0 0 38 6 0 0
output:
789741538
result:
ok "789741538"
Test #30:
score: 0
Accepted
time: 13ms
memory: 19508kb
input:
1 42 0 0 25 0 1 33 0 0 0 29 0 0 0 35 0 0 7 39 0 31 0 0 42 0 0 0 2 0 38 22 14 0 0 0 0 0 28 24 0 0 0 0
output:
394131909
result:
ok "394131909"
Test #31:
score: 0
Accepted
time: 1234ms
memory: 47380kb
input:
1 50 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:
333255637
result:
ok "333255637"
Test #32:
score: 0
Accepted
time: 1016ms
memory: 44068kb
input:
1 49 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:
22735711
result:
ok "22735711"
Test #33:
score: 0
Accepted
time: 829ms
memory: 40952kb
input:
1 48 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:
15964537
result:
ok "15964537"
Test #34:
score: 0
Accepted
time: 16ms
memory: 19656kb
input:
1 49 45 0 29 21 37 5 17 49 33 1 9 0 0 7 0 0 0 47 0 27 43 0 19 3 35 22 6 38 30 0 0 18 0 0 26 0 0 0 0 8 0 0 32 44 0 28 36 4 0
output:
146325999
result:
ok "146325999"
Test #35:
score: 0
Accepted
time: 16ms
memory: 19848kb
input:
1 49 0 0 0 45 13 29 0 0 25 49 17 0 0 11 43 27 19 0 0 23 0 39 15 47 31 0 48 16 8 40 0 0 0 0 36 0 0 0 0 0 30 0 46 0 42 10 0 34 0
output:
657627892
result:
ok "657627892"
Test #36:
score: 0
Accepted
time: 92ms
memory: 28108kb
input:
1 49 0 0 0 0 0 0 11 47 0 0 0 44 0 0 0 0 0 0 0 49 14 0 0 0 0 0 0 0 0 36 0 0 0 27 0 0 0 0 0 26 43 1 0 0 41 0 0 0 0
output:
472948359
result:
ok "472948359"
Test #37:
score: 0
Accepted
time: 1007ms
memory: 44136kb
input:
1 49 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 37 0 30 0 0 33
output:
741412713
result:
ok "741412713"
Test #38:
score: 0
Accepted
time: 16ms
memory: 19632kb
input:
1 50 12 0 28 20 4 36 8 0 24 16 0 32 0 0 0 30 46 14 50 18 0 2 0 42 10 41 0 0 49 0 1 33 0 37 21 0 0 29 11 43 27 0 0 0 0 0 0 0 7 0
output:
602640125
result:
ok "602640125"
Test #39:
score: 0
Accepted
time: 11ms
memory: 19512kb
input:
1 50 19 35 3 0 43 0 0 0 39 15 0 0 0 0 9 0 1 0 0 21 5 37 29 13 0 34 0 50 18 0 10 42 6 0 22 30 0 0 0 0 0 48 16 32 28 12 44 20 0 36
output:
72847122
result:
ok "72847122"
Test #40:
score: 0
Accepted
time: 93ms
memory: 28904kb
input:
1 50 0 0 0 0 0 0 33 44 0 14 0 0 0 0 0 0 31 0 0 0 0 32 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 46 0 0 19
output:
776829897
result:
ok "776829897"
Test #41:
score: 0
Accepted
time: 42ms
memory: 23544kb
input:
1 50 0 0 0 0 0 28 0 2 0 0 0 0 0 7 0 0 0 0 0 29 0 0 0 0 17 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 0
output:
954784168
result:
ok "954784168"