제출 #485545

#제출 시각아이디문제언어결과실행 시간메모리
485545ak2006아름다운 순열 (IZhO12_beauty)C++14
0 / 100
5 ms1228 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } int main() { setIO(); int n; cin>>n; vi a(n),cnt2(n),cnt3(n); vvb adj(n,vb(n,false)); for (int i = 0;i<n;i++){ cin>>a[i]; int x = a[i]; while (x > 0){ cnt2[i] += (x%2 == 1); x /= 2; } x = a[i]; while (x > 0){ cnt3[i] += (x%3 == 1); x /= 3; } } for (int i = 0;i<n;i++){ for (int j = 0;j<n;j++){ if (i == j)continue; adj[i][j] = (cnt2[i] == cnt2[j] or cnt3[i] == cnt3[j]); } } vvi dp(n,vi(1<<n,0)); for (int i = 0;i<n;i++) dp[i][(1<<i)] = 1; for (int mask = 0;mask<(1<<n);mask++){ for (int i = 0;i<n;i++){ if (!(mask & (1<<i)))continue; for (int j = 0;j<n;j++){ if (adj[i][j]) dp[i][mask] += dp[j][mask - (1<<i)]; } } } int ans = 0; for (int i = 0;i<n;i++) ans += dp[i][(1<<n) - 1]; cout<<ans<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...