QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #482168 | #4222. 题 | weiguoliang | 40 | 380ms | 1003720kb | C++14 | 2.4kb | 2024-07-17 17:52:08 | 2024-07-17 17:52:08 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 20
#define mod 1000000007
using namespace std;
ll n,a[N];
struct node{
ll w;
friend bool operator+=(node &a,node b){
return a.w=(a.w+b.w)%mod;
}
friend node operator*(node a,ll b){
return {a.w*b%mod};
}
}dp[2][N][N][N][N][N][N];
/*后三位分别为：
1 3
2 1
3 2
要求为：
1 3 2
2 1 3
3 2 1
*/
void g1(ll i,ll k,ll j,ll o,ll l,ll r,ll x){
dp[i+1&1][k+1][j][o][l][r][x]+=dp[i&1][k][j][o][l][r][x];
if(j)dp[i+1&1][k][j-1][o][l][r+1][x]+=dp[i&1][k][j][o][l][r][x]*j;
if(x)dp[i+1&1][k][j][o][l][r][x-1]+=dp[i&1][k][j][o][l][r][x]*x;
}
void g2(ll i,ll k,ll j,ll o,ll l,ll r,ll x){
dp[i+1&1][k][j+1][o][l][r][x]+=dp[i&1][k][j][o][l][r][x];
if(o)dp[i+1&1][k][j][o-1][l][r][x+1]+=dp[i&1][k][j][o][l][r][x]*o;
if(l)dp[i+1&1][k][j][o][l-1][r][x]+=dp[i&1][k][j][o][l][r][x]*l;
}
void g3(ll i,ll k,ll j,ll o,ll l,ll r,ll x){
dp[i+1&1][k][j][o+1][l][r][x]+=dp[i&1][k][j][o][l][r][x];
if(k)dp[i+1&1][k-1][j][o][l+1][r][x]+=dp[i&1][k][j][o][l][r][x]*k;
if(r)dp[i+1&1][k][j][o][l][r-1][x]+=dp[i&1][k][j][o][l][r][x]*r;
}
ll jie(ll n){
return n?jie(n-1)*n%mod:1;
}
int main(){ll i,j,k,o,x,l,r,t;
char c;
cin>>t;
while(t--){memset(dp,0,sizeof(dp));
cin>>n;
for(i=1;i<=n*3;i++)cin>>c,a[i]=c-'0';
dp[0][0][0][0][0][0][0].w=1;
for(i=0;i<n*3;i++){
for(k=0;k<=min(i,n);k++){
for(j=0;j+k<=min(i,n);j++){
for(o=0;o+k+j<=min(i,n);o++){
for(l=0;l+o+k+j<=n&&l*2+o+k+j<=i;l++){
for(r=0;r*2+l*2+o+k+j<=i&&r+l+o+k+j<=n;r++){
for(x=0;(x+r+l)*2+o+k+j<=i&&x+r+l+o+k+j<=n;x++){
if(!a[i+1])g1(i,k,j,o,l,r,x),g2(i,k,j,o,l,r,x),g3(i,k,j,o,l,r,x);
else if(a[i+1]==1)g1(i,k,j,o,l,r,x);
else if(a[i+1]==2)g2(i,k,j,o,l,r,x);
else g3(i,k,j,o,l,r,x);
dp[i&1][k][j][o][l][r][x].w=0;
}
}
}
}
}
}
}
cout<<dp[n*3&1][0][0][0][0][0][0].w*jie(n)%mod<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 358ms
memory: 1003656kb
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: 352ms
memory: 1003592kb
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: 355ms
memory: 1003716kb
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: 380ms
memory: 1003712kb
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: 0
Wrong Answer
time: 352ms
memory: 1003628kb
input:
5 6 000121310223223210 7 033221120002010100230 7 000003020000010302010 7 000010002020302300100 7 030100002033300000000
output:
26853120 120 3 1 1
result:
wrong answer 2nd lines differ - expected: '152413083', found: '120'
Test #6:
score: 0
Wrong Answer
time: 358ms
memory: 1003656kb
input:
5 9 120332011311030220200103301 10 200003200103011232000202201120 10 000000201330030030101000003000 10 020000002032000000200000100002 10 100200322001000000320000002010
output:
1 18 1 1 1
result:
wrong answer 1st lines differ - expected: '963757075', found: '1'
Test #7:
score: 0
Wrong Answer
time: 360ms
memory: 1003720kb
input:
5 13 000000000000000000000000000000000000000 12 000000000000000000000000000000000000 11 000000000000000000000000000000000 10 000000000000000000000000000000 9 000000000000000000000000000
output:
1 1 1 1 1
result:
wrong answer 1st lines differ - expected: '856865849', found: '1'
Test #8:
score: 0
Wrong Answer
time: 344ms
memory: 1003712kb
input:
5 15 331110203302222220331213331310312220103030021 16 001301022200100032010330002213000300220033210033 16 020002030002000330003200030010000000000100002300 16 320000001003222000003000003000300010323113200020 16 000203000000000000010100000000000000002000210000
output:
0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '70336694', found: '0'
Test #9:
score: 0
Wrong Answer
time: 344ms
memory: 1003652kb
input:
5 17 221001103220113003322101120223031133120301212031002 18 201000020000000010323100000333030002012000213100030001 18 013203020100001021200030003102000130000002330303302120 18 010003030200000200100000002000000000000302000203103300 18 000001000132020000200321023010000000000000000132210300
output:
0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '821788453', found: '0'
Test #10:
score: 0
Wrong Answer
time: 327ms
memory: 1003612kb
input:
5 18 331110100201233220121012022130200011112133012123201012 19 221011310310012302220013020123002132313030023020101110230 19 202000300003001300011000011021320001000300320020302022103 19 010030200000000000300300310000001302002000010230000330020 19 000000000000031000000000131200020001000020000001020000...
output:
0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '171958822', found: '0'