답안 #881116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881116 2023-11-30T15:34:17 Z alexdd 아름다운 순열 (IZhO12_beauty) C++17
0 / 100
0 ms 348 KB
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int cnt2[25];
int cnt3[25];
long long dp[1100000][20][2];
int calc_cnt2(int x)
{
    int rez=0;
    for(int i=0;i<30;i++)
    {
        if(((1<<i)&x))
            rez++;
    }
    return rez;
}
int calc_cnt3(int x)
{
    int rez=0;
    while(x>0)
    {
        if(x%3==1)
            rez++;
        x/=3;
    }
    return rez;
}
signed main()
{
    cin>>n;
    int a;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        cnt2[i] = calc_cnt2(a);
        cnt3[i] = calc_cnt3(a);
    }
    for(int config=1;config<(1<<n);config++)
    {
        for(int cur=0;cur<n;cur++)
        {
            if(((1<<cur)&config)==0)
                continue;
            int cate=0;
            for(int ult=0;ult<n;ult++)
            {
                if(ult!=cur && ((1<<ult)&config))
                {
                    cate++;
                    if(cnt2[ult]==cnt2[cur] || cnt3[ult]==cnt3[cur])
                    {
                        dp[config][cur][1] += dp[config-(1<<cur)][ult][0] + dp[config-(1<<cur)][ult][1];
                    }
                    else
                    {
                        dp[config][cur][0] += dp[config-(1<<cur)][ult][1];
                    }
                }
            }
            if(cate==0)
            {
                dp[config][cur][0] = 1;
                dp[config][cur][1] = 0;
            }
        }
    }
    long long sum=0;
    for(int ult=0;ult<n;ult++)
        sum += dp[(1<<n)-1][ult][1];
    cout<<sum;
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -