제출 #768227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768227		Ahmed57	아름다운 순열 (IZhO12_beauty)	C++17	100 / 100	2443 ms	164540 KiB

beauty

#include<bits/stdc++.h>

using namespace std;
long long n,arr[21],bi[21],ti[21];
long long dp[(1<<20)][20];
long long solve(int mask,int la){
    if(mask==(1<<n)-1)return 1;
    if(dp[mask][la]!=-1)return dp[mask][la];
    long long c1 = 0;
    for(int i = 0;i<n;i++){
        if(mask&(1<<i))continue;
        if(mask==0||bi[i]==bi[la]||ti[i]==ti[la]){
            c1+=solve(mask|(1<<i),i);
        }
    }
    return dp[mask][la] = c1;
}
int main(){
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>arr[i];
        for(int j = 29;j>=0;j--){
            if(arr[i]&(1<<j)){
                bi[i]++;
            }
        }
        long long tmp = arr[i];
        long long ans = 1;
        for(int j = 1;j<=19;j++)ans*=3;
        for(long long j = 19;j>=0;j--){
            int z = 0;
            while(tmp>=ans){
                tmp-=ans;z++;
            }
            ans/=3;
            if(z==1){
                ti[i]++;
            }
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<solve(0,0)<<endl;
}

• Subtask 1: 100 / 100