题解 P3226 【[HNOI2012]集合选数】

## [原文地址](https://www.cnblogs.com/bcoier/p/10788835.html) 题目要求若出现x，则不能出现2x，3x 所以我们考虑构造一个矩阵 $1\ 2\ 4 \ 8……$ $3\ 6\ 12\ 24……$ $9\ 18\ 36……$ $……$ 不难发现，对于一个矩阵，若我选择了一个数x，则在矩阵内该数的相邻格子都不能选，题目就被转化成了[玉米田](https://www.luogu.org/problemnew/show/P1879)了，可以用状压DP解决 但是直接做是不对的，比如5就没有出现在这个序列中 所以我们可以构造多个矩阵，用乘法原理统计答案即可 ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);//freopen(#a".out","w",stdout) #define int long long #define inf 123456789 #define mod 1000000001 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define drep(i, s, t) for(re int i = t; i >= s; -- i) #define mem(k, p) memset(k, p, sizeof(k)) #define maxn 100005 int n, m, a[20][20], g[1 << 15], vis[maxn], H, L[20], dp[20][1 << 15], ans = 1; il void martix(int x) { H = 0; rep(i, 1, 18) { a[i][1] = (i == 1) ? x : a[i - 1][1] * 2; if(a[i][1] > n) break; ++ H, L[i] = vis[a[i][1]] = 1; rep(j, 2, 11) { a[i][j] = a[i][j - 1] * 3; if(a[i][j] > n) break; L[i] = j, vis[a[i][j]] = 1; } } } il int solve() { rep(i, 0, (1 << L[1]) - 1) dp[1][i] = g[i]; rep(i, 2, H) { rep(j, 0, (1 << L[i]) - 1) { if(!g[j]) continue; dp[i][j] = 0; rep(k, 0, (1 << L[i - 1]) - 1) { if(g[k] && (k & j) == 0) dp[i][j] += dp[i - 1][k]; } } } int t = 0; rep(i, 0, (1 << L[H]) - 1) t = (t + dp[H][i]) % mod; return t; } signed main() { n = read(); rep(i, 0, (1 << 11) - 1) g[i] = !(i & (i << 1)); rep(i, 1, n) if(!vis[i]) martix(i), ans = ans * solve() % mod; printf("%lld", ans); return 0; } ```