Submission #1169926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169926		mnbvcxz123	아름다운 순열 (IZhO12_beauty)	C++20	100 / 100	746 ms	127556 KiB

beauty

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

constexpr int N=20;
bool g[N+5][N+5];
ll dp[N+5][(1<<N)+5];

int f(int x){
    int ret=0;
    while(x){
        if(x%3==1)++ret;
        x/=3;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int&i:a)cin>>i;
    for(int i=0;i<n;++i)g[i][i]=1;
    for(int i=0;i<n;++i)
        for(int j=0;j<i;++j)
            if(f(a[i])==f(a[j]) or __builtin_popcount(a[i])==__builtin_popcount(a[j]))g[i][j]=g[j][i]=1;
    for(int i=0;i<n;++i)
        dp[i][1<<i]=1;
    for(int mask=0;mask<(1<<n);++mask)
        for(int last=0;last<n;++last)
            if(mask>>last&1)
                for(int nxt=0;nxt<n;++nxt){
                    if(mask>>nxt&1)continue;
                    if(!g[last][nxt])continue;
                    dp[nxt][mask|(1<<nxt)]+=dp[last][mask];
                }
    ll ret=0;
    for(int i=0;i<n;++i)
        ret+=dp[i][(1<<n)-1];
    cout<<ret<<'\n';
}

• Subtask 1: 100 / 100