#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 305;
const int mod = 1e9 + 7;
int dp[N][N][N];
void adun(int &a, int b)
{
a += b;
if (a >= mod)
a -= mod;
}
int inm(int a, int b)
{
ll c = 1ll * a * b;
c %= mod;
return c;
}
///dp[i][j][k] = nr moduri daca a,b au i in comun
/// b,c au j in comun
/// c,a au k in comun
/**
op
1) a NU are ce sa ii dea lui b => a = 0 => i + k = 0
2) a -> b una pe care o are b => i posibilitati, i--
3) a -> b una pe care o are c => k posibilitati, j++ k--
tb macar o op 2 ca s sa scada
**/
int pos;
void op1(int i, int j, int k)
{
if (i + k != 0)
pos = 0;
}
void op2(int &i, int j, int k)
{
pos *= i;
i--;
}
void op3(int i, int &j, int &k)
{
pos *= k;
j++;
k--;
}
int vc[3][N];
int x[3][3];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, t;
cin >> n >> t;
dp[0][0][0] = 1;
for (int s = 1; s <= 6 * n; s++)
for (int i = 0; i <= 3 * n && i <= s; i++)
for (int j = 0; j <= 3 * n && j + i <= s; j++)
{
int k = s - i - j;
if (i + k > 3 * n || i + j > 3 * n || i + k > 3 * n)
continue;
for (int ab = 1; ab <= 3; ab++)
for (int bc = 1; bc <= 3; bc++)
for (int ca = 1; ca <= 3; ca++)
{
if (ab != 2 && bc != 2 && ca != 2)
continue;
pos = 1;
int I = i, J = j, K = k;
if (ab == 1)
op1(I, J, K);
else
if (ab == 2)
op2(I, J, K);
else
op3(I, J, K);
if (I < 0 || J < 0 || K < 0)
continue;
if (!pos)
continue;
if (bc == 1)
op1(J, K, I);
else
if (bc == 2)
op2(J, K, I);
else
op3(J, K, I);
if (I < 0 || J < 0 || K < 0)
continue;
if (!pos)
continue;
if (ca == 1)
op1(K, I, J);
else
if (ca == 2)
op2(K, I, J);
else
op3(K, I, J);
if (I < 0 || J < 0 || K < 0)
continue;
if (!pos)
continue;
adun(dp[i][j][k], inm(pos, dp[I][J][K]));
}
}
while(t--)
{
for (int i = 0; i < 3; i++)
for (int j = 1; j <= 3 * n; j++)
vc[i][j] = 0;
for (int i = 0; i < 3; i++)
for (int j = 1; j <= 2 * n; j++)
{
int nr;
cin >> nr;
vc[i][nr] = 1;
}
for (int i = 0; i < 3; i++)
for (int j = i + 1; j < 3; j++)
{
x[i][j] = 0;
for (int k = 1; k <= 3 * n; k++)
if (vc[i][k] && vc[j][k])
x[i][j]++;
}
cout << dp[x[0][1]][x[1][2]][x[0][2]] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
16 ms |
2800 KB |
Output is correct |
| 5 |
Correct |
240 ms |
14544 KB |
Output is correct |
| 6 |
Correct |
402 ms |
20572 KB |
Output is correct |
| 7 |
Correct |
747 ms |
27824 KB |
Output is correct |
| 8 |
Correct |
948 ms |
35952 KB |
Output is correct |
| 9 |
Correct |
1364 ms |
45268 KB |
Output is correct |
| 10 |
Correct |
1821 ms |
54592 KB |
Output is correct |
