제출 #382222

#제출 시각아이디문제언어결과실행 시간메모리
382222vishesh312아름다운 순열 (IZhO12_beauty)C++17
0 / 100
55 ms4716 KiB
#include "bits/stdc++.h" using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; */ #define all(x) begin(x), end(x) #define sz(x) (int)x.size() using ll = long long; const int mod = 1e9+7; void solve(int tc) { int n; cin >> n; vector<int> v(n); for (auto &x : v) cin >> x; vector<vector<int>> dp(n, vector<int>(1<<n)); for (int i = 0; i < n; ++i) { dp[i][1<<i] = 1; } vector<int> a(n); for (int i = 0; i < n; ++i) { int x = v[i]; while (x) { a[i] += (x % 3 == 1); x /= 3; } } for (int mask = 0; mask < (1<<n); ++mask) { for (int i = 0; i < n; ++i) { if (mask&(1<<i)) { for (int j = 0; j < n; ++j) { if (!(mask&(1<<j)) and (__builtin_popcount(v[i]) == __builtin_popcount(v[j]) or a[i] == a[j])) { dp[j][mask|(1<<j)] += dp[i][mask]; } } } } } ll ans = 0; for (int i = 0; i < n; ++i) { ans += dp[i][(1<<n)-1]; } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tc = 1; //cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...