HAOI2018 奇怪的背包

发表于 更新于 分类于

「HAOI2018」奇怪的背包

其实这题和背包一点关系都没有。

题目要求解方程的解数，

\[\sum x-ia-i\equiv w\pmod p\]

根据裴蜀定理，方程有解当且仅当\(\gcd(a-1,a-2,\cdots,a-n,p)\mid w\)

于是设\(f[i][j]\)表示前\(i\)个数的与\(p\)的最大公约数是\(j\)时的方案数，转移只需要枚举当前这个选不选，不需要考虑具体选了多少个。

因为\(p\)的约数个数不多，我们应该开一个数组映射一下\(p\)的约数作为转移状态的第二维。

如果两个物体和\(p\)的\(\gcd\)相等的话，我们可以把它们一起转移，只需要乘上一个非空子集个数的系数就可以了。

最后统计答案，其实我们要统计的是\(\sum_{i\mid w}f[m][i]\)，\(m\)是\(p\)约数个数

即\(i\mid p \wedge i\mid w\)，相当于\(i\mid \gcd(p,w)\)

于是可以先预处理出\(w\mid p\)时的答案，即可以\(\mathjaxcal{O}((m^2 + n + q) \log p)-\mathjaxcal{O}(1)\)的时间复杂度完成此题。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2000 + 5, MOD = 1e9 + 7;
int d[N], n, m, p, q, bit[1000005], f[N][N], cnt[N], ans[N];

int pos(int x) {
	return lower-bound(d + 1, d + m + 1, x) - d;
}
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
    scanf("%d %d %d", &n, &q, &p);
    bit[0] = 1;
    for (int i = 1; i <= n; i++) bit[i] = bit[i - 1] * 2ll % MOD;
    for (int i = 1; i <= p / i; i++) if (p % i == 0) {
        d[++m] = i;
        if (i * i != p) d[++m] = p / i;
    }
    sort(d + 1, d + m + 1);
    for (int i = 1, x; i <= n; i++) {
    	scanf("%d", &x);
    	cnt[pos(gcd(x, p))]++;
    }
    f[0][m] = 1;
    for (int i = 1; i <= m; i++)
    	for (int j = 1; j <= m; j++) {
    		int g = pos(gcd(d[i], d[j]));
    		f[i][g] = (f[i][g] + f[i - 1][j] * 1ll * (bit[cnt[i]] - 1) % MOD) % MOD;
    		f[i][j] = (f[i][j] + f[i - 1][j]) % MOD;
    	}
    for (int i = 1; i <= m; i++)
    	for (int j = 1; j <= i; j++) if (d[i] % d[j] == 0) {
    		ans[i] = (ans[i] + f[m][j]) % MOD;
    	}
    for (int i = 1, x; i <= q; i++) scanf("%d", &x), printf("%d\n", ans[pos(gcd(p, x))]);
    return 0;
}