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;
}