#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 200, mod = 1000000007;
vector<vector<vector<int>>> dp;
void dfs(array<int, 3> &cnt, int ind, int ways, bool red) {
if(ind == 3) {
if(red) {
// cout << "to: " << cnt[0] << " " << cnt[1] << " " << cnt[2] << "\n";
dp[cnt[0]][cnt[1]][cnt[2]] = (dp[cnt[0]][cnt[1]][cnt[2]] + ways) % mod;
}
return;
}
if(cnt[ind]) {
--cnt[ind];
dfs(cnt, ind + 1, ways * (cnt[ind] + 1) % mod, 1);
++cnt[ind];
}
int bf = (ind + 2) % 3, bbf = (ind + 1) % 3;
if(cnt[bf]) {
--cnt[bf];
++cnt[bbf];
dfs(cnt, ind + 1, ways * (cnt[bf] + 1) % mod, red);
++cnt[bf];
--cnt[bbf];
}
if(!cnt[ind] and !cnt[bf]) {
dfs(cnt, ind + 1, ways, red);
}
}
void solve(int n){
vector <set<int> > hands(3);
for(int j = 0; j < 3; j++) {
for(int i = 0; i < 2 * n; i++) {
int in;
cin >> in;
hands[j].insert(in);
}
}
vector <int> cnt(3);
for(int j = 0; j < 3; j++) {
for(auto it:hands[j]) {
if(hands[(j + 1) % 3].count(it)) {
cnt[j]++;
}
}
}
int a = cnt[0], b = cnt[1], c = cnt[2];
vector<vector<vector<int>>> ndp(n * 3 + 1, vector<vector<int>> (n * 3 + 1, vector<int>(n * 3 + 1, 0)));
dp = ndp;
dp[a][b][c] = 1;
for(int sum = n * 3; sum >= 0; sum--) for(int j = sum; j >= 0; j--) for(int k = sum - j; k >= 0; k--){
int i = sum - j - k;
if(i < 0) continue;
// cout << i << " " << j << " " << k << " = " << dp[i][j][k] << "\n";
array <int, 3> tmp = {i, j, k};
dfs(tmp, 0, dp[i][j][k], 0);
}
cout << dp[0][0][0] << "\n";
}
int32_t main(){
fast
int t=1, n;
cin >> n >> t;
while(t--) solve(n);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
3 ms |
996 KB |
Output is correct |
4 |
Correct |
23 ms |
4188 KB |
Output is correct |
5 |
Correct |
854 ms |
55968 KB |
Output is correct |
6 |
Correct |
1448 ms |
95572 KB |
Output is correct |
7 |
Execution timed out |
2054 ms |
150840 KB |
Time limit exceeded |
8 |
Execution timed out |
2059 ms |
223664 KB |
Time limit exceeded |
9 |
Execution timed out |
2085 ms |
317124 KB |
Time limit exceeded |
10 |
Execution timed out |
2081 ms |
422416 KB |
Time limit exceeded |