QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #482321 | #4222. 题 | yqh2025 | 100 ✓ | 446ms | 313676kb | C++14 | 1.6kb | 2024-07-17 18:55:05 | 2024-07-17 18:55:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20,mod=1e9+7;
int n,f[2][N][N][N][N][N][N];
char ch[N*3];
void sol(){
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 g=0;a+b+c+d+e+g<=n;g++){
f[0][a][b][c][d][e][g]=0;
f[1][a][b][c][d][e][g]=0;
}
}
}
}
}
}
scanf("%lld%s",&n,ch+1);
f[0][0][0][0][0][0][0]=1;
for(int I=1;I<=n*3;I++){
int i=I&1,j=i^1;
// memset(f[i],0,sizeof(f[i]));
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 g=0;a+b+c+d+e+g<=n;g++){
int &x=f[i][a][b][c][d][e][g];x=0;
if(ch[I]=='1'||ch[I]=='0'){
x=(x+((a>0)?f[j][a-1][b][c][d][e][g]:0)+((e>0&&b<n)?f[j][a][b+1][c][d][e-1][g]*(b+1)%mod:0)+((g<n)?f[j][a][b][c][d][e][g+1]*(g+1)%mod:0));
}
if(ch[I]=='2'||ch[I]=='0'){
x=(x+((b>0)?f[j][a][b-1][c][d][e][g]:0)+((g>0&&c<n)?f[j][a][b][c+1][d][e][g-1]*(c+1)%mod:0)+((d<n)?f[j][a][b][c][d+1][e][g]*(d+1)%mod:0));
}
if(ch[I]=='3'||ch[I]=='0'){
x=(x+((c>0)?f[j][a][b][c-1][d][e][g]:0)+((d>0&&a<n)?f[j][a+1][b][c][d-1][e][g]*(a+1)%mod:0)+((e<n)?f[j][a][b][c][d][e+1][g]*(e+1)%mod:0));
}
x%=mod;
}
}
}
}
}
}
}
int ans=f[(n*3)&1][0][0][0][0][0][0];
for(int i=1;i<=n;i++)ans=ans*i%mod;
printf("%lld\n",ans);
}
signed main(){
int t;cin>>t;
while(t--)sol();
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 0ms
memory: 10092kb
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: 0ms
memory: 14024kb
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: 0ms
memory: 18188kb
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: 0ms
memory: 34964kb
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: 0ms
memory: 56264kb
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: 7ms
memory: 97292kb
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: 32ms
memory: 151020kb
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: 167ms
memory: 224664kb
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: 329ms
memory: 283884kb
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: 446ms
memory: 313676kb
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