Submission #648120

#	Time	Username	Problem	Language	Result	Execution time	Memory
648120		starchan	Beautiful row (IZhO12_beauty)	C++17	100 / 100	854 ms	127592 KiB

beauty

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int cnt2(int n)
{
	int ans = 0;
	while(n)
	{
		ans+=(n%2==1);
		n/=2;
	}
	return ans;
}
int cnt3(int n)
{
	int ans = 0;
	while(n)
	{
		ans+=(n%3==1);
		n/=3;
	}
	return ans;
}
int dp[20][1ll<<20];
signed main()
{
	fast();
	int n;
	cin >> n;
	vector<vector<int>> adj(n);
	vector<in> a(n);
	for(int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a[i] = {cnt2(x), cnt3(x)};
		for(int j = 0; j < i; j++)
		{
			if(a[i].f == a[j].f || a[i].s == a[j].s)
			{
				adj[i].pb(j);
				adj[j].pb(i);
			}
		}
	}
	int ans = 0;
	for(int j = 1; j < (1ll<<n); j++)
	{
		for(int i = 0; i < n; i++)
		{
			if((j^(1ll<<i)) > j)
				continue;
			int k = j^(1ll<<i);
			if(k==0)
			{
				dp[i][j] = 1;
				continue;
			}
			dp[i][j] = 0;
			for(int v: adj[i])
			{
				if((k^(1ll<<v)) > k)
					continue;
				dp[i][j]+=dp[v][k];
			}
		}
	}
	for(int i = 0; i < n; i++)
		ans+=dp[i][(1ll<<n)-1];
	cout << ans;
	return 0;
}	

• Subtask 1: 100 / 100