#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 205
#define fi first
#define se second
set<int> a,b;
int dp[3][lim][lim][lim][2];
inline int add(int x,int y){
if(x+y>=mod)return x+y-mod;
return x+y;
}
inline int carp(int x,int y){
return (x%mod)*(y%mod)%mod;
}
inline int f(int kim,int ab,int bc,int ac,int tut){
if(ab==0 && bc==0 && ac==0)return 1;
if(~dp[kim][ab][bc][ac][tut])return dp[kim][ab][bc][ac][tut];
int cev=0;
if(kim==0){
if(ab==0 && ac==0){
cev=add(cev,f(kim+1,ab,bc,ac,0));
}
else{
if(ab)cev=add(cev,carp(ab,f(kim+1,ab-1,bc,ac,1)));
if(ac)cev=add(cev,carp(ac,f(kim+1,ab,bc+1,ac-1,0)));
}
}
else if(kim==1){
if(bc==0 && ab==0){
cev=add(cev,f(kim+1,ab,bc,ac,tut));
}
else{
if(bc)cev=add(cev,carp(bc,f(kim+1,ab,bc-1,ac,1)));
if(ab)cev=add(cev,carp(ab,f(kim+1,ab-1,bc,ac+1,tut)));
}
}
else{
if(ac==0 && bc==0){
if(tut)cev=add(cev,f(0,ab,bc,ac,1));
}
else{
if(ac)cev=add(cev,carp(ac,f(0,ab,bc,ac-1,1)));
if(tut && bc)cev=add(cev,carp(bc,f(0,ab+1,bc-1,ac,0)));
}
}
return dp[kim][ab][bc][ac][tut]=cev;
}
int32_t main(){
faster
int n,t;cin>>n>>t;
while(t--){
memset(dp,-1,sizeof(dp));
a.clear();
b.clear();
int ab=0,ac=0,bc=0;
for(int i=1;i<=2*n;i++){
int x;cin>>x;
a.insert(x);
}
for(int i=1;i<=2*n;i++){
int x;cin>>x;
if(a.count(x))ab++;
b.insert(x);
}
for(int i=1;i<=2*n;i++){
int x;cin>>x;
if(b.count(x))bc++;
if(a.count(x))ac++;
}
cout<<f(0,ab,bc,ac,0)<<'\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
405052 KB |
Output is correct |
2 |
Correct |
235 ms |
404820 KB |
Output is correct |
3 |
Correct |
240 ms |
404820 KB |
Output is correct |
4 |
Correct |
240 ms |
404988 KB |
Output is correct |
5 |
Correct |
360 ms |
405076 KB |
Output is correct |
6 |
Correct |
404 ms |
404884 KB |
Output is correct |
7 |
Correct |
432 ms |
405068 KB |
Output is correct |
8 |
Correct |
492 ms |
405080 KB |
Output is correct |
9 |
Correct |
566 ms |
405332 KB |
Output is correct |
10 |
Correct |
651 ms |
405076 KB |
Output is correct |