题解：SP707 TFSETS - Triple-Free Sets

思路

注意到，如果把每个数视作一个点，并把每个点 $x$ 向 $2x,3x$ 连边，那么问题转化为这张图的独立集计数。

再使劲瞪一眼，发现这张图是一个网格图，每个连通块的左上角是一个不是 $2$ 或 $3$ 的倍数的数 $x$，第 $i$ 行第 $j$ 列是 $x\times 3^i\times 2^j$。例如下图：

1 --- 2 --- 4 --- 8
|     |     |
3 --- 6 --- 12
|
9

5 --- 10

7

11

即为 $n=12$ 时的图。

注意到每个连通块的大小至多是 $O(\log_3 n\times \log_2 n)$ 的，其中 $\log_3 n\le 10$，最多只有 $11$ 行，可以考虑状压 DP。

具体地，处理出每一个合理的列状态，压成一个数，设 $dp_{i,s}$ 表示第 $i$ 列的状态为 $s$ 时，前 $i$ 列的独立集数量。转移直接暴力转移，复杂度 $O(S^2\log_2 n)$，其中 $S$ 为状态总数，可估算为 $2^{\log_3 n}=n^{\log_3 2}$，实际上远没有这么多，实测有 $S=233$。

对于多个连通块，一个想法是把每个连通块都做一遍 DP，复杂度约为 $O(nS^2\log n)$，看着很大，实际上完全跑不满，可以通过本题弱化版 P3226。

不过对于多测，这种做法还是太勉强了。不难注意到另一件事情：左上角为 $x$ 的连通块，其等价于左上角为 $1$ 的连通块在 $n’=\displaystyle\lfloor\frac{n}{x}\rfloor$ 时的答案。

所以只要处理 $f_i$ 表示 $n’=i$ 时，左上角为 $1$ 的连通块的答案，最终结果即为：

$$\prod_{i=1}^nf_{\lfloor\frac{n}{i}\rfloor}^{[2\nmid i \land 3\nmid i]}$$

时间复杂度 $O(S^2\log^3 n+Tn)$，而且完全跑不满，轻松通过。

后一部分应该可以使用数论分块降到更低。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5, maxs = 255, p = 1e9 + 1;

vector<int> st[15], pre[maxs];
int a[15], tot = 0, inv[maxs];

void dfs(int x, int dep){
    st[dep].push_back(++ tot), inv[tot] = x;
    for(int i = dep + 1; i <= 11; i ++){
        if(a[i - 1]) continue;
        a[i] = 1;
        dfs(x + (1 << i - 1), i);
        a[i] = 0;
    }
}
void init(){
    dfs(0, 0);
    for(int i = 1; i <= tot; i ++){
        for(int j = 1; j <= tot; j ++){
            if(inv[i] & inv[j]) continue;
            pre[i].push_back(j);
        }
    }
}
int len[25], dp[25][maxs];
void insert(int x){
    len[x] ++;
    for(int i = 0; i < st[len[x]].size(); i ++){
        int j = st[len[x]][i];
        for(int o = 0; o < pre[j].size(); o ++) dp[x][j] = (dp[x][j] + dp[x - 1][pre[j][o]]) % p;
    }
    while(++ x <= 18){
        for(int l = 0; l <= len[x]; l ++){
            for(int i = 0; i < st[l].size(); i ++){
                int j = st[l][i];
                dp[x][j] = 0;
                for(int o = 0; o < pre[j].size(); o ++) dp[x][j] = (dp[x][j] + dp[x - 1][pre[j][o]]) % p;
            }
        }
    }
}
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
int f[maxn];

int main(){
    init();
    q.push(make_pair(1, 1));
    int t = 1;
    for(int i = 0; i <= 18; i ++) dp[i][1] = 1;
    while(!q.empty() && q.top().first <= 1e5){
        int x = q.top().first, row = q.top().second;
        q.pop();
        for(int i = t; i < x; i ++) f[i] = dp[18][1];
        insert(row);
        t = x;
        if(row == 1) q.push(make_pair(x * 3, 1));
        q.push(make_pair(x * 2, row + 1));
    }
    for(int i = t; i <= 1e5; i ++) f[i] = dp[18][1];
    int T;
    scanf("%d", &T);
    while(T --){
        int n;
        scanf("%d", &n);
        int ans = 1;
        for(int i = 1; i <= n; i ++) if((i % 2) && (i % 3)) ans = 1ll * ans * f[n / i] % p;
        printf("%d\n", ans);
    }
    return 0;
}