#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 220,mod = 1e9+7,inf = 1e9+10,maxm = (1 << 18)+10;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k /= 2;
}
return z;
}
int n,T;
int dp[N][N][N][3][2];
pll vis[N*3];
void f(int i,int j,int k,int fl,int b){
if (dp[i][j][k][fl][b] != -1) return;
if (!i && !j && !k){
dp[i][j][k][fl][b] = 1;
return;
}
dp[i][j][k][fl][b] = 0;
if (!fl){
if (!i && !k){
f(i,j,k,1,0);
dp[i][j][k][0][0] = dp[i][j][k][1][0];
return;
}
if (i){
f(i-1,j,k,1,1);
dp[i][j][k][fl][b] = 1ll*i*dp[i-1][j][k][1][1]%mod;
}
if (k){
f(i,j+1,k-1,1,0);
dp[i][j][k][0][0] = mkay(dp[i][j][k][0][0],1ll*k*dp[i][j+1][k-1][1][0]%mod);
}
return;
}
if (fl == 1){
if (!i && !j){
f(i,j,k,2,b);
dp[i][j][k][1][b] = dp[i][j][k][2][b];
return;
}
if (i){
f(i-1,j,k+1,2,b);
dp[i][j][k][fl][b] = 1ll*i*dp[i-1][j][k+1][2][b]%mod;
}
if (j){
f(i,j-1,k,2,1);
dp[i][j][k][fl][b] = mkay(dp[i][j][k][fl][b],1ll*j*dp[i][j-1][k][2][1]%mod);
}
return;
}
if (!j && !k){
if (b == 1){
f(i,j,k,0,0);
dp[i][j][k][2][1] = dp[i][0][0][0][0];
}
else dp[i][j][k][2][0] = 0;
return;
}
if (!b){
if (!k){
dp[i][j][k][2][0] = 0;
return;
}
f(i,j,k-1,0,0);
dp[i][j][k][2][0] = 1ll*k*dp[i][j][k-1][0][0]%mod;
return;
}
if (k){
f(i,j,k-1,0,0);
dp[i][j][k][2][1] = 1ll*k*dp[i][j][k-1][0][0]%mod;
}
if (j){
f(i+1,j-1,k,0,0);
dp[i][j][k][2][1] = mkay(dp[i][j][k][2][1],1ll*dp[i+1][j-1][k][0][0]*j%mod);
}
}
int main(){
memset(dp,-1,sizeof dp);
cin >> n >> T;
int n2 = 2*n,n3 = 3*n;
while (T--){
rep(i,0,n3+1) vis[i] = {-1,-1};
int t0 = 0,t1 = 0,t2 = 0;
rep(j,0,3){
rep(i,0,n2){
int x;
cin >> x;
if (vis[x].X == -1) vis[x].X = j;
else{
vis[x].Y = j;
if (vis[x].X == 0 && vis[x].Y == 1) t0++;
else if (vis[x].X == 1 && vis[x].Y == 2) t1++;
else if (vis[x].X == 0 && vis[x].Y == 2) t2++;
}
}
}
f(t0,t1,t2,0,0);
cout << dp[t0][t1][t2][0][0] << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
250232 KB |
Output is correct |
| 2 |
Correct |
88 ms |
250272 KB |
Output is correct |
| 3 |
Correct |
90 ms |
250296 KB |
Output is correct |
| 4 |
Correct |
91 ms |
250236 KB |
Output is correct |
| 5 |
Correct |
101 ms |
250348 KB |
Output is correct |
| 6 |
Correct |
107 ms |
250340 KB |
Output is correct |
| 7 |
Correct |
116 ms |
250336 KB |
Output is correct |
| 8 |
Correct |
129 ms |
250336 KB |
Output is correct |
| 9 |
Correct |
143 ms |
250260 KB |
Output is correct |
| 10 |
Correct |
162 ms |
250288 KB |
Output is correct |
