QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #152685 | #4222. 题 | james1BadCreeper | 100 ✓ | 469ms | 503768kb | C++14 | 2.6kb | 2023-08-28 17:03:42 | 2023-08-28 17:03:43 |
Judging History
answer
#include <bits/stdc++.h>
#define DEBUG ;
using namespace std;
const int P = 1000000007;
inline void add(int &x, int k, int t) { x = (x + 1ll * k * t) % P; }
int n;
char a[65];
int f[2][20][20][20][20][20][20]; // 1 2 3 1,3 2,1 3,2
int main(void) {
int T; scanf("%d", &T);
while (T--) {
memset(f, 0, sizeof f); f[0][0][0][0][0][0][0] = 1;
scanf("%d%s", &n, a + 1);
for (int i = 1; i <= n * 3; ++i) a[i] -= '0';
for (int i = 1; i <= n * 3; ++i) {
DEBUG;
for (int A = 0; A <= n; ++A) for (int B = 0; A + B <= n; ++B) for (int C = 0; A + B + C <= n; ++C) for (int D = 0; A + B + C + D <= n; ++D) for (int E = 0; A + B + C + D + E <= n; ++E) for (int F = 0; A + B + C + D + E + F <= n; ++F) f[1][A][B][C][D][E][F] = 0;
DEBUG;
for (int A = 0; A <= n; ++A) for (int B = 0; A + B <= n; ++B) for (int C = 0; A + B + C <= n; ++C) for (int D = 0; A + B + C + D <= n; ++D) for (int E = 0; A + B + C + D + E <= n; ++E) for (int F = 0; A + B + C + D + E + F <= n; ++F)
if (f[0][A][B][C][D][E][F]) {
int t = f[0][A][B][C][D][E][F];
if (a[i] == 0 || a[i] == 1) {
if (A < n) add(f[1][A + 1][B][C][D][E][F], 1, t);
if (B && E < n) add(f[1][A][B - 1][C][D][E + 1][F], B, t);
if (F) add(f[1][A][B][C][D][E][F - 1], F, t);
}
if (a[i] == 0 || a[i] == 2) {
if (B < n) add(f[1][A][B + 1][C][D][E][F], 1, t);
if (C && F < n) add(f[1][A][B][C - 1][D][E][F + 1], C, t);
if (D) add(f[1][A][B][C][D - 1][E][F], D, t);
}
if (a[i] == 0 || a[i] == 3) {
if (C < n) add(f[1][A][B][C + 1][D][E][F], 1, t);
if (A && D < n) add(f[1][A - 1][B][C][D + 1][E][F], A, t);
if (E) add(f[1][A][B][C][D][E - 1][F], E, t);
}
}
DEBUG;
for (int A = 0; A <= n; ++A) for (int B = 0; A + B <= n; ++B) for (int C = 0; A + B + C <= n; ++C) for (int D = 0; A + B + C + D <= n; ++D) for (int E = 0; A + B + C + D + E <= n; ++E) for (int F = 0; A + B + C + D + E + F <= n; ++F) f[0][A][B][C][D][E][F] = f[1][A][B][C][D][E][F];
DEBUG;
}
int ans = f[0][0][0][0][0][0][0];
for (int i = 1; i <= n; ++i) ans = 1ll * ans * i % P;
printf("%d\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 176ms
memory: 503640kb
input:
5 1 123 1 100 1 000 1 300 1 010
output:
0 1 3 1 1
result:
ok 5 lines
Test #2:
score: 10
Accepted
time: 171ms
memory: 503616kb
input:
5 1 303 2 000320 2 002000 2 002020 2 020020
output:
0 36 60 12 12
result:
ok 5 lines
Test #3:
score: 10
Accepted
time: 193ms
memory: 503704kb
input:
5 2 110133 3 200010000 3 002002200 3 300000000 3 000000130
output:
0 5940 540 15120 7560
result:
ok 5 lines
Test #4:
score: 10
Accepted
time: 196ms
memory: 503552kb
input:
5 5 000000000000000 4 000000000000 3 000000000 2 000000 1 000
output:
864823720 29937600 45360 180 3
result:
ok 5 lines
Test #5:
score: 10
Accepted
time: 182ms
memory: 503608kb
input:
5 6 000121310223223210 7 033221120002010100230 7 000003020000010302010 7 000010002020302300100 7 030100002033300000000
output:
26853120 152413083 939384999 4309685 970165754
result:
ok 5 lines
Test #6:
score: 10
Accepted
time: 183ms
memory: 503764kb
input:
5 9 120332011311030220200103301 10 200003200103011232000202201120 10 000000201330030030101000003000 10 020000002032000000200000100002 10 100200322001000000320000002010
output:
963757075 290911546 487693965 730680478 984422198
result:
ok 5 lines
Test #7:
score: 10
Accepted
time: 186ms
memory: 503620kb
input:
5 13 000000000000000000000000000000000000000 12 000000000000000000000000000000000000 11 000000000000000000000000000000000 10 000000000000000000000000000000 9 000000000000000000000000000
output:
856865849 574346463 607449787 883895867 88660419
result:
ok 5 lines
Test #8:
score: 10
Accepted
time: 295ms
memory: 503704kb
input:
5 15 331110203302222220331213331310312220103030021 16 001301022200100032010330002213000300220033210033 16 020002030002000330003200030010000000000100002300 16 320000001003222000003000003000300010323113200020 16 000203000000000000010100000000000000002000210000
output:
70336694 482512438 740138646 212387388 427674884
result:
ok 5 lines
Test #9:
score: 10
Accepted
time: 388ms
memory: 503768kb
input:
5 17 221001103220113003322101120223031133120301212031002 18 201000020000000010323100000333030002012000213100030001 18 013203020100001021200030003102000130000002330303302120 18 010003030200000200100000002000000000000302000203103300 18 000001000132020000200321023010000000000000000132210300
output:
821788453 589132243 303959134 648206569 571580782
result:
ok 5 lines
Test #10:
score: 10
Accepted
time: 469ms
memory: 503632kb
input:
5 18 331110100201233220121012022130200011112133012123201012 19 221011310310012302220013020123002132313030023020101110230 19 202000300003001300011000011021320001000300320020302022103 19 010030200000000000300300310000001302002000010230000330020 19 000000000000031000000000131200020001000020000001020000...
output:
171958822 242716134 229925968 914555153 59496792
result:
ok 5 lines
Extra Test:
score: 0
Extra Test Passed