HNOI2012 集合选数

wjh15101051's space

卧薪尝胆，厚积薄发。

HNOI2012 集合选数

Date: Fri Aug 10 22:35:04 CST 2018

In Category: NoCategory

Description：

对于 $n$ ，求出 $\{1,2,3,\dots,n\}$ 满足若 $x$ 在子集中，则 $2x$ 和 $3x$ 不在子集中的子集个数。

$1\le n \le 100000$

Solution：

打一张表：

$1\ 2\ 4\ 8$

$3\ 6\ 12\ 24$

$9\ 18\ 36\ 72$

发现这张表中每个数字都只出现了一次，且相邻的数不能同时被选，最多只有 $log_3n\approx 12$ 行，于是可以状压 $DP$ ，注意要排掉包含 $>n$ 的数的状态。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

#define MOD 1000000001

typedef long long ll;

bool vis[MAXN];

ll f[20][1 << 15];

ll dp(ll t)

{

	ll tot = 1;

	for(ll i = t;i * 3 <= n;i = i * 3,++tot);

	tot = (1 << tot);

	ll p = 1;

	ll ans = 0;

	f[0][0] = 1;

	for(ll i = t;i <= n;i = i * 2)

	{

		for(ll j = i;j <= n;j = j * 3)vis[j] = true;

		for(ll j = 0;j < tot;++j)

		{

			f[p][j] = 0;

			if((j & (j << 1)) || (j & (j >> 1)))continue;

			bool tag = false;

			for(ll b = 1,cur = i;b < tot;b = b << 1,cur = cur * 3)

			{

				if((j & b) && cur > n)

				{

					tag = true;

					break;

				}

			}

			if(tag)continue;

			for(ll k = 0;k < tot;++k)

			{

				if((k & (k << 1)) || (k & (k >> 1)))continue;

				if(j & k)continue;

				f[p][j] = (f[p][j] + f[p - 1][k]) % MOD;

			}

		}

		++p;

	}

	--p;

	for(ll i = 0;i < tot;++i)ans = (ans + f[p][i]) % MOD;

	return ans;

}

int main()

{

	scanf("%d",&n);

	ll res = 1;

	for(int i = 1;i <= n;++i)

	{

		if(!vis[i])res = res * dp(i) % MOD;

	}

	cout << res << endl;

	return 0;

}

In tag: DP-状压DP

wjh15101051