Submission #1098484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098484		0pt1mus23	Beautiful row (IZhO12_beauty)	C++14	0 / 100	7 ms	4308 KiB

beauty

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

#define int long long
#define ins insert      
#define pb push_back

#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
#define _ << " " <<
mt19937 rng(time(0));

const int mod = 998244353,
        sze = (1<<20) +23,
        inf = LLONG_MAX,    
        L = 31;

int dp[sze][30];
int bt(int n){
    int c=0;
    while(n){
        c+= ( (n%3) ==1);
        n/=3;
    }
    return c;
}
void _0x0(){
    int n;
    cin>>n;
    vector<int> olur[n];
    vector<int> arr(n);
    vector<int> bar(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
        bar[i]=bt(arr[i]);
        olur[i].resize(n,0);
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(bar[i]==bar[j] || __builtin_popcount(arr[i]) == __builtin_popcount(arr[j]) ){
                olur[i][j]=1;
            }
        }
    }
    // dp[0][0]=1;
    for(int i=0;i<n;i++){
        dp[(1<<i)][i] = 1;
    }
    for(int mask=0;mask<(1<<n);mask++){
        for(int last=0;last<n;last++){
            if(mask & (1<<last)){
                for(int ext=0;ext<n;ext++){
                    if(! (mask & (1<<ext)) && olur[last][ext]){
                        // cout<<mask _ " last: " _ last _ "next:" _ ext _ "=>" _ (mask|(1<<ext)) _ dp[mask][last] <<endl;
                        dp[mask | (1<<ext)][ext] += dp[mask][last];
                    }
                }

            }
        }
    }

    int ans=accumulate(dp[(1<<n) -1],dp[(1<<n) -1]+n+1,0);
    putr(ans);

}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin>>tt;
    while(tt--){
        _0x0();
    }
 
    return 0;
}

• Subtask 1: 0 / 100