Description
给你两个正整数 $n$ 和 $k$，问你在 $1∼n$ 中选不超过 $k$ 个数，它们的积不含平方质因子的方案数。
Solution
由于在 $\sqrt{n}$ 以内的质数个数只有 9 个，因此考虑把当前乘积含 $\sqrt{n}$ 以内质因子的情况用一个二进制数 $S$ 来表示，S 从低位往高位数的第 $i$ 个二进制位为 0 / 1 表示当前的乘积不含有 / 含有一个第 $i$ 小的质数这一因子。
显然不可能含有两个及以上，否则它们的积就含平方质因子了。
对于含同一大于 $\sqrt{n}$ 的质因子的数，我们把它们归到同一类，因此显然在同一类中我们最多只能够取一个数。
于是我们想到设 $f_{i, j, S}$ 表示当前取完了质因子 $i$ 所在的这一列，已经选了 $j$ 个数，含 $\sqrt{n}$ 以内的质因子的情况为 $S$ 的方案数。
然后发现 $i$ 那一维可以滚动掉，然后随便转移一下即可。
注意 Code 中的 $j$ 那一维要倒着枚举，这个你想一下 01 背包和完全背包转移枚举顺序的区别就明白了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include <cstdio>
#include <cstring>
#define mod 1000000007
#define maxN 510
int f[maxN][1 << 8], g[maxN][maxN];
int state[maxN];
int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19};
int main ()
{
for(int i = 1;i < maxN; i++)
{
int now = i;
for(int j = 0;j <= 7; j++)
{
if(!(now % (prime[j] * prime[j])))
{
state[i] = -1;
break;
}
if(!(now % prime[j]))
{
state[i] |= (1 << j);
now /= prime[j];
}
}
}
int T = 0;
scanf("%d", &T);
const int maxS = (1 << 8) - 1;
while(T--)
{
memset(f, 0, sizeof(f));
int n = 0, k = 0;
scanf("%d %d", &n, &k);
for(int i = 1;i <= n; i++)
{
if(state[i] < 0)
{
continue;
}
int now = i;
for(int j = 0;j <= 7; j++)
{
if(!(now % prime[j]))
{
now /= prime[j];
}
}
if(now > 1)
{
g[now][++g[now][0]] = i;
}
else
{
g[i][++g[i][0]] = i;
}
}
f[0][0] = 1;
for(int i = 1;i <= n; i++)
{
if(g[i][0])
{
for(int j = k - 1;j >= 0; j--)
{
for(int p = 1;p <= g[i][0]; p++)
{
int now = g[i][p];
for(int S = 0;S <= maxS; S++)
{
if(!(S & state[now]))
{
f[j + 1][S | state[now]] += f[j][S];
f[j + 1][S | state[now]] %= mod;
}
}
}
}
}
}
for(int i = 1;i <= n; i++)
{
g[i][0] = 0;
}
int Ans = 0;
for(int i = 1;i <= k; i++)
{
for(int S = 0;S <= maxS; S++)
{
Ans += f[i][S];
Ans %= mod;
}
}
printf("%d\n", Ans);
}
return 0;
}
|