QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #482191 | #4222. 题 | weiguoliang | 100 ✓ | 783ms | 561764kb | C++14 | 2.7kb | 2024-07-17 18:06:21 | 2024-07-17 18:06:21 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 20
#define mod 1000000007
using namespace std;
ll n,a[N*3];
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--){
cin>>n;
for(i=1;i<=n*3;i++)cin>>c,a[i]=c-'0';
for(k=0;k<20;k++)for(j=0;j+k<20;j++)for(o=0;o+k+j<20;o++)for(l=0;l+o+k+j<20;l++)for(r=0;r+l+o+k+j<20;r++)for(x=0;x+r+l+o+k+j<20;x++)dp[0][k][j][o][l][r][x].w=dp[1][k][j][o][l][r][x].w=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;
}
}
}
}
}
}
for(k=0;k<20;k++)for(j=0;j+k<20;j++)for(o=0;o+k+j<20;o++)for(l=0;l+o+k+j<20;l++)for(r=0;r+l+o+k+j<20;r++)for(x=0;x+r+l+o+k+j<20;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: 11ms
memory: 561196kb
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: 12ms
memory: 557520kb
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: 15ms
memory: 556920kb
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: 16ms
memory: 558940kb
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: 28ms
memory: 557004kb
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: 50ms
memory: 556620kb
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: 91ms
memory: 561764kb
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: 323ms
memory: 557132kb
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: 597ms
memory: 559784kb
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: 783ms
memory: 557436kb
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