#include <bits/stdc++.h>
//#include "bingo.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long n,t,p;
int memo[101][101][101][3][2];
long long dp(int ab,int ac,int bc,int guy,bool use){
//a is 0 and 1, b is 0 and 2, c is 1 and 2
if (ab==0 && ac==0 && bc==0) return 1;
if (guy==0){
if (!use) return 0;
use=false;
}
if (memo[ab][ac][bc][guy][use]!=-1){
return memo[ab][ac][bc][guy][use];
}
long long res=0;
if (guy==0){
if (ab+ac==0){
res=dp(ab,ac,bc,1,use);
res%=p;
}
else {
if (ab>0) res+=dp(ab-1,ac,bc,1,true)*(long long) ab;
res%=p;
if (ac>0) res+=dp(ab,ac-1,bc+1,1,use)*(long long) ac;
res%=p;
}
}
else if (guy==1){
if (ab+bc==0){
res=dp(ab,ac,bc,2,use);
res%=p;
}
else {
if (bc>0) res+=dp(ab,ac,bc-1,2,true)*(long long) bc;
res%=p;
if (ab>0) res+=dp(ab-1,ac+1,bc,2,use)*(long long) ab;
res%=p;
}
}
else {
if (ac+bc==0){
res=dp(ab,ac,bc,0,use);
res%=p;
}
else {
if (ac>0) res+=dp(ab,ac-1,bc,0,false)*(long long) ac;
res%=p;
if (bc>0) res+=dp(ab+1,ac,bc-1,0,false)*(long long) bc;
res%=p;
}
}
//cout<<a<<' '<<b<<' '<<c<<' '<<guy<<' '<<use<<' '<<res<<'\n';
return memo[ab][ac][bc][guy][use]=res%p;
}
pair<int,int> arr[301];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>t;
memset(memo,-1,sizeof(memo));
p=1e9+7;
while (t--){
cin>>n;
for (int i=1;i<=n*3;i++){
arr[i]=mp(-1,-1);
}
for (int i=0;i<3;i++){
for (int j=0;j<n*2;j++){
int x;
cin>>x;
if (arr[x].first==-1) arr[x].first=i;
else arr[x].second=i;
}
}
int ab=0,ac=0,bc=0;
//a is 0 and 1, b is 0 and 2, c is 1 and 2
for (int i=1;i<=n*3;i++){
if (arr[i].first==arr[i].second) continue;
if (arr[i].first>arr[i].second){
swap(arr[i].first,arr[i].second);
}
if (arr[i]==mp(0,1)) ab++;
else if (arr[i]==mp(0,2)) ac++;
else bc++;
}
//cout<<a<<' '<<b<<' '<<c<<'\n';
cout<<dp(ab,ac,bc,0,true)<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24576 KB |
Output isn't correct |
| 2 |
Incorrect |
13 ms |
24576 KB |
Output isn't correct |
| 3 |
Incorrect |
15 ms |
24576 KB |
Output isn't correct |
| 4 |
Incorrect |
13 ms |
24576 KB |
Output isn't correct |
| 5 |
Incorrect |
14 ms |
24576 KB |
Output isn't correct |
| 6 |
Incorrect |
16 ms |
24576 KB |
Output isn't correct |
| 7 |
Incorrect |
14 ms |
24576 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
24576 KB |
Output isn't correct |
| 9 |
Incorrect |
14 ms |
24576 KB |
Output isn't correct |
| 10 |
Incorrect |
16 ms |
24576 KB |
Output isn't correct |
