제출 #89282

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
89282	2018-12-11 09:30:48	turbat	아름다운 순열 (IZhO12_beauty)	C++14	100 / 100	1792 ms	205924 KiB

beauty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std; 
     
long long n, m, a[25], dp[1<<21][25], ans, cnt[25], cnt1[25];
     
int main (){  
  cin >> n;
    for (int i = 0;i < n;i++) {
      cin >> a[i];
      cnt[i] = __builtin_popcount(a[i]);
      m = a[i];
      while (m){
        if (m % 3 == 1) cnt1[i]++;
        m /= 3;
      }
    }
    for (int i = 0;i < n;i++) dp[1 << i][i] = 1;
    for (int i = 0;i < (1 << n);i++)
      for (int j = 0;j < n;j++)
        for (int o = 0;o < n;o++)
          if (!(i & 1<<o) && (cnt[j] == cnt[o] || cnt1[j] == cnt1[o]))
            dp[i|(1<<o)][o] += dp[i][j];
    for (int i = 0;i < n;i++) ans += dp[(1<<n) - 1][i];
    cout << ans;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 100 / 100