题目大意
从集合 ${ 1, 2, \cdots, n }$ 中选出一个子集，满足其中不存在两个数互相是两倍或三倍关系。求选的方案总数$\bmod 10^9 + 1$ 的结果。
数据范围：$n \le 10^5$。
思路分析
Yet another problem about independent set.
我们把数视作结点，矛盾视作边，那么发现所有矛盾形成了多个网格图，且行数不超过 $17$，列数不超过 $11$。于是直接 DP，然后再相乘即可。
时间复杂度 $O(17 \times 11 \times 2^{11})$。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 1e5, maxh = 17, maxw = 11, maxs = 1 << maxw, mod = 1e9 + 1; |
6 | int n, pw2[maxh + 3], pw3[maxw + 3], h, w, a[maxh + 3][maxw + 3], dp[maxh + 3][maxw + 3][maxs + 3]; |
7 | bool vis[maxn + 3]; |
8 | |
9 | void prework() { |
10 | pw2[0] = pw3[0] = 1; |
11 | for (int i = 1; i <= maxh; i++) { |
12 | pw2[i] = pw2[i - 1] * 2; |
13 | } |
14 | for (int i = 1; i <= maxw; i++) { |
15 | pw3[i] = pw3[i - 1] * 3; |
16 | } |
17 | } |
18 | |
19 | void upd(int &x, int y) { |
20 | x += y, x < mod ? 0 : x -= mod; |
21 | } |
22 | |
23 | int solve(int x) { |
24 | for (int i = 1; i <= h; i++) { |
25 | for (int j = 1; j <= w; j++) { |
26 | a[i][j] = 0; |
27 | } |
28 | } |
29 | h = w = 0; |
30 | for (int i = 0; pw2[i] * x <= n; i++) { |
31 | h = max(h, i + 1); |
32 | for (int j = 0; pw2[i] * pw3[j] * x <= n; j++) { |
33 | w = max(w, j + 1); |
34 | a[i + 1][j + 1] = pw2[i] * pw3[j] * x; |
35 | vis[pw2[i] * pw3[j] * x] = true; |
36 | } |
37 | } |
38 | dp[0][w][0] = 1; |
39 | for (int msk = 1; msk < 1 << w; msk++) { |
40 | dp[0][w][msk] = 0; |
41 | } |
42 | for (int i = 1; i <= h; i++) { |
43 | for (int msk = 0; msk < 1 << w; msk++) { |
44 | dp[i][0][msk] = dp[i - 1][w][msk]; |
45 | } |
46 | for (int j = 1; j <= w; j++) { |
47 | for (int msk = 0; msk < 1 << w; msk++) { |
48 | dp[i][j][msk] = 0; |
49 | } |
50 | for (int msk = 0; msk < 1 << w; msk++) { |
51 | if (!dp[i][j - 1][msk]) continue; |
52 | upd(dp[i][j][msk & (((1 << w) - 1) ^ (1 << (j - 1)))], dp[i][j - 1][msk]); |
53 | if (a[i][j] && (~msk >> (j - 1) & 1) && (j == 1 || (~msk >> (j - 2) & 1))) { |
54 | upd(dp[i][j][msk | (1 << (j - 1))], dp[i][j - 1][msk]); |
55 | } |
56 | } |
57 | } |
58 | } |
59 | int ans = 0; |
60 | for (int msk = 0; msk < 1 << w; msk++) { |
61 | upd(ans, dp[h][w][msk]); |
62 | } |
63 | return ans; |
64 | } |
65 | |
66 | int main() { |
67 | prework(); |
68 | scanf("%d", &n); |
69 | int ans = 1; |
70 | for (int i = 1; i <= n; i++) if (!vis[i]) { |
71 | ans = 1ll * ans * solve(i) % mod; |
72 | } |
73 | printf("%d\n", ans); |
74 | return 0; |
75 | } |