「SNOI2017」遗失的答案

发表于
https://loj.ac/problem/2257

题目链接

「SNOI2017」遗失的答案

做法

先判断有无解（ $ L \mod G = 0 $ ），然后将 $ n /= G, L /= G $ 。
由于 $ n \leq 1e8 $ ，所以每个数最多有 $ 8 $ 个不同的质因数。
令 $ L = p_{1}^{a_1}p_{2}^{a_2} \dots p_{t}^{a_t} $ ，则素数 $ p_i $ 的指数上界为 $ a_i $ 。
由题意得对于每个质因数所选的数既有恰好达到上界，由于恰好为下界的。由于状态数为 $ 16 $ ，所以可以状压。
可以通过 $ dfs $ 处理出所有 $ x $ 使得 $ x \leq n $ 且 $ x = p_{1}^{b_1}p_{2}^{b_2} \dots p_{t}^{b_t} (b_i \leq a_i) $ ，然后将 $ x $ 分类统计。
于是问题转化为给出一个集合，求或为全集的方案数。
设 $ f_s $ 表示或为 $ s $ 的方案数。
设 $ g_s = \sum_{i \in s} f_i = 2^{cnt_s} - 1 $ 表示或为 $ s $ 子集的方案数。
容斥得 $ f_s = \sum_{i \in s} (-1)^{|s| - |i|} g_i $ 。 

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
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1000010;
int n, L, G, m, mx;
int p[20], lp, cnt[20];
int ba[N], g[N], sz[N];
map<int, int> ans;

inline int add(const int &x, const int &y) { return x + y < mod ? x + y : x + y - mod; }
inline int sub(const int &x, const int &y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(const int &x, const int &y) { return (ll)x * y % mod; }
void dfs(int u, int state, int w) {
	if(w > n) return ; if(u > lp) { ++g[state]; return ; }
	dfs(u + 1, state | (1 << u - 1), w);
	rep(i, 1, cnt[u] - 1) w *= p[u], dfs(u + 1, state, w);
	dfs(u + 1, state | (1 << u + lp - 1), w * p[u]);
}
int calc(int state) {
	int res = 0;
	rep(i, 0, mx) {
		if((state & i) != state) continue;
		if(sz[i] & 1) res = sub(res, ba[g[i] - 1]);
		else res = add(res, ba[g[i] - 1]);
	}
	return res;
}
int main() {
	scanf("%d%d%d%d", &n, &G, &L, &m);
	if(L % G) { for(; m; --m, puts("0")); return 0; }
	L /= G, n /= G; ll tt = L;
	for(int i = 2; i * i <= tt; i++) if(tt % i == 0) {
		p[++lp] = i; for(; tt % i == 0; tt /= i) ++cnt[lp];
	}
	if(tt > 1) p[++lp] = tt, ++cnt[lp];
	mx = (1 << lp + lp) - 1, dfs(1, 0, 1);
	rep(i, 1, lp + lp) rep(j, 0, mx)
		if(j & (1 << i - 1)) g[j] += g[j ^ (1 << i - 1)];
	ba[0] = 1; rep(i, 1, g[mx]) ba[i] = add(ba[i - 1], ba[i - 1]);
	rep(i, 1, mx) sz[i] = sz[i >> 1] + (i & 1);
	for(int x; m; --m) {
		scanf("%d", &x); if(x % G) { puts("0"); continue; }
		x /= G; if(L % x || x > n) { puts("0"); continue; }
		if(ans.find(x) != ans.end()) { printf("%d\n", ans[x]); continue; }
		int state = 0, t = 0, tmp = x;
		for(int i = 1; i <= lp; i++) {
			for(; x % p[i] == 0; x /= p[i], ++t);
			if(!t) state |= (1 << i - 1);
			if(t == cnt[i]) state |= (1 << i + lp - 1);
			t = 0;
		}
		printf("%d\n", ans[tmp] = calc(state));
	}
	return 0;
}