洛谷P3226 [HNOI2012] 集合选数 题解

题目链接：P3226 [HNOI2012] 集合选数

题意：

《集合论与图论》这门课程有一道作业题，要求同学们求出 $\{ 1, 2, 3, 4, 5 \}$ 的所有满足以下条件的子集：若 $x$ 在该子集中，则 $2x$ 和 $3x$ 不能在该子集中。

同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 $n \le 10^5$，如何求出 $\{1,2,\ldots ,n\}$ 的满足上述约束条件的子集的个数（只需输出对 $10^9+1$ 取模的结果），现在这个问题就交给你了。

输入格式：

只有一行，其中有一个正整数 $n$。$30 \%$ 的数据满足 $n \le 20$。

输出格式：

仅包含一个正整数，表示 $\{1,2,\ldots ,n\}$ 有多少个满足上述约束条件的子集。

数据范围：

对于 $100 \%$ 的数据，$1 \le n \le 10^5$。

考虑构造如下系数矩阵

$$\begin{matrix} 1&2&4&8&16&32&\cdots \\[6pt]3&6&12&24&48&96&\cdots \\[6pt]9&18&36&72&\cdots \\[6pt]27&\cdots \end{matrix}$$

其中 $1$ 表示 $x$ ，$2$ 表示 $2x$ 。初始 $x=1$ 。

我们对每个没有在前一个矩阵出现过的 $x$ 都构造这样的矩阵。

那么问题就变成了，对于每个矩阵，选择矩阵中的一些数，要求不能选相邻的数的方案数

把每个矩阵的方案数乘起来就是答案。求法考虑状压dp即可，详见代码。

时间复杂度 $\mathcal{O}(\mathrm{ok})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 1;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))
#define M 20
#define mx 262143

bool vis[mx + 5];
int n, m, sz[M], a[M][M], f[M][mx + 5], g[mx + 5];
void init(int x)
{
    rep(i, 1, 11)
    {
        a[i][1] = ((i == 1) ? x : a[i - 1][1] * 3);
        if(a[i][1] > n) break;
        m = i; vis[a[i][1]] = true; int t = 1;
        rep(j, 2, 18)
        {
            a[i][j] = a[i][j - 1] * 2; if(a[i][j] > n) break;
            t = j; vis[a[i][j]] = true;
        }
        sz[i] = (1 << t) - 1;
    }
}
int solve(int x)
{
    init(x); int res = 0;
    rep(i, 0, sz[1]) f[1][i] = g[i];
    rep(i, 2, m) rep(j, 0, sz[i]) if(g[j])
    {
        f[i][j] = 0;
        rep(k, 0, sz[i - 1]) if(g[k] && (!(k & j)))
            add(f[i][j], f[i - 1][k]);
    }
    rep(i, 0, sz[m]) add(res, f[m][i]);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; int ans = 1;
    rep(i, 0, mx) g[i] = !((i << 1) & i);
    rep(i, 1, n) if(!vis[i]) ans = ans * solve(i) % mod;
    cout << ans << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/b42lqqan