|
いちごみるく |
|
6*6ぐらいなら0.031secで終わりました。
7*7に75秒かかりますが61479419904000と正しい答えを出せます #include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define endl "\n" long long N, M, subM; int memo[5040][7]; bool Check[7][7]; long long dfs(int d) { if (d == (N - 2)) { return 1; } long long ret = 0; rep2(i, (d + 1)*subM, (d + 2)*subM) { bool b = true; rep(j, N) { if (Check[j][memo[i][j]]) { b = false; } } if (b) { rep(j, N) { Check[j][memo[i][j]] = true; } ret += dfs(d + 1); rep(j, N) { Check[j][memo[i][j]] = false; } } } return ret; } int main() { cin >> N; M = 1; vector<int> v; rep(i, N) { v.push_back(i); M *= (i + 1); } subM = M / N; int now = 0; do { rep(i, N) { memo[now][i] = v[i]; } now++; } while (next_permutation(v.begin(), v.end())); rep(i, N) { Check[i][i] = true; } long long ans = M * subM; ans *= dfs(0); cout << ans << endl; } |
|
1月22日（金） 19:15:56
50057 |