oj.uz

답안 #338515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338515 2020-12-23T10:06:25 Z talant117408 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 935 ms 189284 KB 
/*
    Code written by Talant I.D.
*/
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int graph[23][23], n;
ll dp[(1<<20)][23];

int main(){
    do_not_disturb
    
    cin >> n;
    vector <ll> v(n), bin(n), tern(n);
    for(auto &to : v) cin >> to;
    
    for(int i = 0; i < n; i++){
        int to = v[i];
        for(int bit = 30; bit >= 0; bit--)
            if(to&(1<<bit)) bin[i]++;
        for(int bit = 30; bit >= 0; bit--){
            if(to/(ll)pow(3ll, bit) == 1) tern[i]++;
            to %= (ll)pow(3ll, bit);
        }
    }
    
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(bin[i] == bin[j] || tern[i] == tern[j]){
                graph[i][j] = graph[j][i] = 1;
            }
        }
    }
    
    for(int i = 0; i < n; i++){
        dp[(1<<i)][i] = 1;
    }
    
    for(int mask = 1; mask < (1<<n); mask++){
        if(__builtin_popcount(mask) == 1) continue;
        for(int i = 0; i < n; i++){
            if(mask&(1<<i)){
                for(int j = 0; j < n; j++){
                    if(i == j) continue;
                    if(mask&(1<<j) && graph[i][j]){
                        dp[mask][i] += dp[(mask^(1<<i))][j];
                    }
                }
            }
        }
    }
    
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += dp[(1<<n)-1][i];
    }
    cout << ans;
    
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 10 ms 3308 KB Output is correct
12 Correct 11 ms 3308 KB Output is correct
13 Correct 39 ms 12140 KB Output is correct
14 Correct 203 ms 47492 KB Output is correct
15 Correct 177 ms 47480 KB Output is correct
16 Correct 197 ms 47596 KB Output is correct
17 Correct 208 ms 47584 KB Output is correct
18 Correct 207 ms 47596 KB Output is correct
19 Correct 935 ms 189284 KB Output is correct
20 Correct 803 ms 189112 KB Output is correct