#include <bits/stdc++.h>
#define DIM 310
#define MOD 1000000007
using namespace std;
int dp[DIM][DIM][DIM],fa[DIM*2],fb[DIM*2],fc[DIM*3],a[DIM],b[DIM],c[DIM];
int t,n,i,j,k;
int main (){
//ifstream cin ("fishing.in");
//ofstream cout ("fishing.out");
cin>>n>>t;
for (;t--;){
memset (fa,0,sizeof fa);
memset (fb,0,sizeof fb);
memset (fc,0,sizeof fc);
for (i=1;i<=2*n;i++){
cin>>a[i];
fa[a[i]]++;
}
for (i=1;i<=2*n;i++){
cin>>b[i];
fb[b[i]]++;
}
for (i=1;i<=2*n;i++){
cin>>c[i];
fc[c[i]]++;
}
int nr_ab = 0, nr_ac = 0, nr_bc = 0;
for (i=1;i<=3*n;i++){
if (fa[i] && fb[i]) /// cate au in comun a si b
nr_ab++;
if (fa[i] && fc[i]) /// cate au in comun a si c
nr_ac++;
if (fb[i] && fc[i]) /// cate au in comun b si c
nr_bc++;
}
memset (dp,0,sizeof dp);
dp[nr_ab][nr_ac][nr_bc] = 1;
for (int sum=nr_ab + nr_ac + nr_bc;sum>=0;sum--){
for (i=0;i<=sum && i<=3*n;i++){
for (j=0;i+j<=sum && j<=3*n;j++){
k = sum - i - j;
if (k > 3*n || !dp[i][j][k]) /// nu am calculat starea asta
continue;
/// A -> B -> C -> A
int nr_ab = i, nr_ac = j, nr_bc = k, sol1, sol2, sol3;
for (int tip_a=0;tip_a<=1;tip_a++){
/// A -> B
if (!tip_a){
sol1 = nr_ab;
nr_ab--;
} else {
sol1 = nr_ac;
nr_ac--, nr_bc++;
}
for (int tip_b=0;tip_b<=1 && sol1;tip_b++){
/// B -> C
if (!tip_b){
sol2 = nr_bc;
nr_bc--;
} else {
sol2 = nr_ab;
nr_ab--, nr_ac++;
}
for (int tip_c=0;tip_c<=1 && sol2;tip_c++){
/// C -> A
if (!tip_c){
sol3 = nr_ac;
nr_ac--;
} else {
sol3 = nr_bc;
nr_bc--, nr_ab++;
}
if (nr_ab + nr_ac + nr_bc < i + j + k && sol3 > 0){
dp[nr_ab][nr_ac][nr_bc] += 1LL * dp[i][j][k] * sol1 % MOD * sol2 % MOD * sol3 % MOD;
if (dp[nr_ab][nr_ac][nr_bc] >= MOD)
dp[nr_ab][nr_ac][nr_bc] -= MOD;
}
(!tip_c) ? (nr_ac++) : (nr_bc++, nr_ab--);
}
(!tip_b) ? (nr_bc++) : (nr_ab++, nr_ac--);
}
/// reverse
(!tip_a) ? (nr_ab++) : (nr_ac++, nr_bc--);
}}}}
cout<<dp[0][0][0]<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
116856 KB |
Output isn't correct |
| 2 |
Incorrect |
118 ms |
116984 KB |
Output isn't correct |
| 3 |
Incorrect |
121 ms |
116984 KB |
Output isn't correct |
| 4 |
Incorrect |
118 ms |
116856 KB |
Output isn't correct |
| 5 |
Incorrect |
231 ms |
116984 KB |
Output isn't correct |
| 6 |
Incorrect |
258 ms |
116856 KB |
Output isn't correct |
| 7 |
Incorrect |
299 ms |
116984 KB |
Output isn't correct |
| 8 |
Incorrect |
353 ms |
117112 KB |
Output isn't correct |
| 9 |
Incorrect |
422 ms |
116984 KB |
Output isn't correct |
| 10 |
Incorrect |
512 ms |
116984 KB |
Output isn't correct |
