HNOI2012 - 集合选数

https://www.luogu.com.cn/problem/P3226

不算难的非显然状压 dp。

首先根据限制条件建图，\((x,2x),(x,3x)\) 连边，表示边上相邻两个点不能同时选，然后一组独立集就是一个可行的集合。

发现画出来的图是若干个部分网格图，每个连通块最小的点都是与 \(6\) 互质的数。具体证明也不是很难。下图是 \(n=20\) 时的图（ps：漏了 11 13 17 三个单点）。

然后发现每个网格图不大（长宽都是 \(log\) 级别的），就可以状压 dp 了。

//P3226
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll P = 1e9 + 1;
const int N = 1e5 + 10;
ll vis[N], f[2][N];
int p[20];

bool chk(int x, int tp){
	for(int i = 0; i < tp - 1; ++ i){
		if((x & (1 << i)) && (x & (1 << (i+1)))){
			return false;
		}
	}
	return true;
}

ll calc(int x){
	if(vis[x]){
		return vis[x];
	}
	memset(p, 0, sizeof(p));
	int ed;
	for(int i = 1, j = 1; (1 << (j-1)) <= x; ++ j){
		i = (1 << (j-1));
		while(i <= x){
			++ p[j];
			i *= 3;
		}
		ed = j;
	}
	memset(f, 0, sizeof(f));
	f[0][0] = 1;
	int tp = 0;
	for(int i = 1; i <= ed; ++ i){
		tp ^= 1;
		memset(f[tp], 0, sizeof(f[tp]));
		for(int j = 0; j < (1 << p[i-1]); ++ j){
			for(int k = 0; k < (1 << p[i]); ++ k){
				if(chk(k, p[i]) && ((j & k) == 0)){
					f[tp][k] = (f[tp][k] + f[tp^1][j]) % P;
				}
			}
		}
	}
	ll rs = 0;
	for(int k = 0; k < (1 << p[ed]); ++ k){
		if(chk(k, p[ed])){
			rs = (rs + f[tp][k]) % P;
		}
	}
	return vis[x] = rs;
}

int main(){
	int n;
	scanf("%d", &n);
	ll ans = 1;
	for(int i = 1; i <= n; ++ i){
		if(i % 2 != 0 && i % 3 != 0){
			ans = ans * calc(n/i) % P;
		}
	}
	printf("%lld\n", ans);
	return 0;
}