SNOI2017

SNOI2017

礼物

考虑如何在矩阵中维护\(i^k\). \[ (i+1)^k=\sum_{j=0}^k\binom{k}{j}i^j \] 所以直接在矩阵里维护一下\(i^0,i^1,\cdots,i^k\)就好了.顺手维护一个前缀和.

复杂度:\(O(k^3\log n)\)

代码:

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*
* 2253.cpp
* This file is part of 2253
*
* Copyright (C) 2019 - ViXbob
*
* 2253 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2253 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2253. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int fac[maxn], ifac[maxn];
ll n, k;

inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

struct Matrix {
int H, W;
vector<vector<int> > mat;
Matrix(int a = 0, int b = 0) {
mat.resize(a);
H = a; W = b;
for(auto &v : mat) v.resize(b);
}

vector<int> &operator [] (const int &x) { return mat[x]; }

Matrix operator * (const Matrix &t) const {
Matrix rnt(H, t.W);
rep(i, 0, H - 1) rep(j, 0, t.W - 1) rep(k, 0, W - 1)
rnt[i][j] = pls(rnt[i][j], 1ll * mat[i][k] * t.mat[k][j] % P);
return rnt;
}

Matrix operator ^ (ll k) const {
Matrix rnt = (*this), x = (*this);
for(ll i = k - 1; i; i >>= 1, x = x * x) if(i & 1) rnt = rnt * x;
return rnt;
}
} A, Trans;

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); k = read();
A = Matrix(1, k + 3); Trans = Matrix(k + 3, k + 3);
rep(i, 0, k + 2) A[0][i] = 1;
fac[0] = 1;
rep(i, 1, 100) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[100] = inv(fac[100]);
dep(i, 99, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
rep(j, 0, k) rep(i, 0, j) Trans[i][j] = C(j, i);
rep(i, 0, k) Trans[i][k + 1] = Trans[i][k + 2] = C(k, i);
Trans[k + 2][k + 1] = 1;
Trans[k + 2][k + 2] = 2;
if(n <= 1) { puts("1"); return 0; }
Trans = Trans ^ (n - 1);
A = A * Trans;
printf("%d\n", A[0][k + 1]);
return 0;
}

一个简单的询问

把这个东西看成一个二维平面,一个点\((x,y)\),当且仅当\(a[x]=a[y]\)时这个点才有贡献.

然后个询问相当于在问左下角的坐标为\((l_1,l_2)\)右上角的坐标为\((r_1,r_2)\)的矩形内有多少有贡献的点.

\(S(a,b,c,d)\)表示左下角为\((a,b)\),右上角为\((c,d)\)的矩形内有贡献的点的个数.则有: \[ S(a,b,c,d)=S(1,1,c,d)-S(1,1,a-1,d)-S(1,1,c,b-1)+S(1,1,a-1,b-1) \] 然后我们直接把一个询问拆成\(4\)个询问.这样对于拆完的询问中就只有两个变量了.

实际上莫队不仅仅可以解决区间询问,实际上莫队的本质是解决了一类只有两种变量的询问.(这个还是比较有启发意义的)

然后直接用莫队搞一下就好了.复杂度:\(O(n\sqrt{n})\)

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
97
/*
* 2254.cpp
* This file is part of 2254
*
* Copyright (C) 2019 - ViXbob
*
* 2254 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2254 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2254. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 1;

int n, a[maxn], Q, be[maxn], B, cnt, con1[maxn], con2[maxn], L, R;
ll CurAns, ans[maxn];

struct Query {
int l, r, type, id;
Query(int a = 0, int b = 0, int c = 0, int d = 0) { l = a; r = b; type = c; id = d; }
bool operator < (const Query &t) const { return be[l] < be[t.l] || (be[l] == be[t.l] && r < t.r); }
} q[maxm];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void add1(int x) { CurAns += con2[a[x]]; con1[a[x]]++; }
inline void del1(int x) { CurAns -= con2[a[x]]; con1[a[x]]--; }
inline void add2(int x) { CurAns += con1[a[x]]; con2[a[x]]++; }
inline void del2(int x) { CurAns -= con1[a[x]]; con2[a[x]]--; }

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n) a[i] = read();
Q = read(); B = sqrt(n);
rep(i, 1, n) be[i] = (i - 1) / B + 1;
rep(i, 1, Q) {
int l = read(), r = read(), L = read(), R = read();
q[++cnt] = Query(r, R, 1, i);
q[++cnt] = Query(r, L - 1, -1, i);
q[++cnt] = Query(l - 1, R, -1, i);
q[++cnt] = Query(l - 1, L - 1, 1, i);
}
sort(q + 1, q + 1 + cnt);
L = R = 0;
rep(i, 1, cnt) {
while(L < q[i].l) L++, add1(L);
while(L > q[i].l) del1(L), L--;
while(R < q[i].r) R++, add2(R);
while(R > q[i].r) del2(R), R--;
ans[q[i].id] += q[i].type * CurAns;
}
rep(i, 1, Q) printf("%lld\n", ans[i]);
return 0;
}

炸弹

把每个炸弹看成图上的一个节点,一个炸弹能引爆另一个炸弹就说明这个节点能到达那个节点.所以一个炸弹能引爆的炸弹的数目就是从这个节点出发能遍历到的节点的个数.

又因为一个节点能到达的节点的编号是一个连续的区间,我们考虑线段树优化建图,然后建出来的是一个有向图.我们缩环后\(\text{Toposort}\)一下就可以求出在有向图上一个节点能到达的节点的个数了.

复杂度\(O(n\log n)\).

代码:

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
* 2255.cpp
* This file is part of 2255
*
* Copyright (C) 2019 - ViXbob
*
* 2255 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2255 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2255. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 2e6 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int LOG = 20;

int n, ans, bcnt, low[maxn], dfn[maxn], coc, st[maxn], top, be[maxn], w[maxn], f[maxn], tot;
int deg[maxn], g[maxn];
bool inq[maxn];
ll a[maxn], r[maxn];
vector<int> G[maxn], SCC[maxn], E[maxn];
map<pair<int, int>, bool> mp;

inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid (l + r >> 1)
inline void Build(int l, int r, int p) {
tot = max(tot, p + n);
if(l == r) return (void)(G[p + n].pb(r));
Build(l, mid, ls); Build(mid + 1, r, rs);
G[p + n].pb(ls + n);
G[p + n].pb(rs + n);
}

inline void Link(int l, int r, int ql, int qr, int p, int x) {
if(l == ql && r == qr) {
G[x].pb(p + n);
// cerr << x << " -> " << "[" << l << ", " << r << "] = " << p + n << endl;
return;
}
if(qr <= mid) Link(l, mid, ql, qr, ls, x);
else if(ql > mid) Link(mid + 1, r, ql, qr, rs, x);
else Link(l, mid, ql, mid, ls, x), Link(mid + 1, r, mid + 1, qr, rs, x);
}
#undef ls
#undef rs
#undef mid

inline void Tarjan(int x) {
dfn[x] = low[x] = ++coc;
inq[x] = 1; st[++top] = x;
// cerr << "x = " << x << endl;
for(auto v : G[x]) {
if(!dfn[v]) {
Tarjan(v);
low[x] = min(low[x], low[v]);
} else if(inq[v]) low[x] = min(low[x], dfn[v]);
}
if(dfn[x] == low[x]) {
++bcnt;
while(inq[x]) {
be[st[top]] = bcnt;
SCC[bcnt].pb(st[top]);
w[bcnt] += (st[top] <= n);
inq[st[top]] = 0; top--;
}
}
}

inline void ReBuild() {
rep(i, 1, tot) for(auto v : G[i]) if(be[v] != be[i] && !mp.count(mp(be[v], be[i])))
E[be[v]].pb(be[i]), deg[be[i]]++, mp[mp(be[v], be[i])] = 1;

}

inline void Toposort() {
queue<int> q;
rep(i, 1, bcnt) if(!deg[i]) q.push(i);
while(q.size()) {
int u = q.front(); q.pop();
f[u] += w[u];
for(auto v : SCC[u]) g[v] = f[u];
for(auto v : E[u]) {
f[v] += f[u];
if(!--deg[v]) q.push(v);
}
}
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n) a[i] = read(), r[i] = read();
Build(1, n, 1);
rep(i, 1, n) {
int L = lower_bound(a + 1, a + 1 + i, a[i] - r[i]) - a;
int R = upper_bound(a + 1 + i, a + 1 + n, a[i] + r[i]) - a - 1;
Link(1, n, L, R, 1, i);
}
rep(i, 1, tot) if(!dfn[i]) Tarjan(i);
ReBuild(); Toposort();
rep(i, 1, n) ans = pls(ans, 1ll * i * g[i] % P);
cout << ans << endl;
return 0;
}

英雄联盟

Solution1:

虽然数目很大,但是钱很小.

我们把用的钱压到状态里去然后直接背包就好了.

Solution2:

\(\text{FBI Warning}\):本方法过于愚蠢,谨慎阅读.

考虑到\(K_i \le 10\).

所以凑出来的数的不同质因子的个数只有\(4\)种(2,3,5,7).

我们直接设\(f[i][j][k][v][l]\)表示考虑了前\(i\)中英雄凑出来的数为\(2^i \times 3^j \times 5^k \times 7^l\)的最小花费.

然后直接\(\text{dp}\)就好了.复杂度:\(O(N\times 58\times 38\times 27\times 23)\).

因为状态严重不满所以跑起来还是挺快的.

代码:

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
97
/*
* 2256.cpp
* This file is part of 2256
*
* Copyright (C) 2019 - ViXbob
*
* 2256 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2256 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2256. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

template <typename T> bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int n, f[2][59][38][27][23], K[maxn], c[maxn], ans = inf;
ll pow2[maxn], pow3[maxn], pow5[maxn], pow7[maxn], m;

inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read();
rep(i, 1, n) K[i] = read();
rep(i, 1, n) c[i] = read();
pow2[0] = pow3[0] = pow5[0] = pow7[0] = 1;
rep(i, 1, 58) pow2[i] = pow2[i - 1] * 2;
rep(i, 1, 37) pow3[i] = pow3[i - 1] * 3;
rep(i, 1, 26) pow5[i] = pow5[i - 1] * 5;
rep(i, 1, 22) pow7[i] = pow7[i - 1] * 7;
memset(f, 0x3f, sizeof(f));
f[0][0][0][0][0] = 0;
rep(i, 0, n) {
int t = i & 1, t0 = t ^ 1;
memset(f[t0], 0x3f, sizeof(f[t0]));
rep(j, 0, 57) rep(k, 0, 36) rep(l, 0, 25) rep(v, 0, 21) if(f[t][j][k][l][v] != inf) {
if(pow2[j] * pow3[k] * pow5[l] * pow7[v] >= m) ans = min(ans, f[t][j][k][l][v]);
else if(i < n) {
f[t0][j][k][l][v] = min(f[t0][j][k][l][v], f[t][j][k][l][v]);
if(K[i + 1] >= 2) chkmin(f[t0][j + 1][k][l][v], f[t][j][k][l][v] + c[i + 1] * 2);
if(K[i + 1] >= 3) chkmin(f[t0][j][k + 1][l][v], f[t][j][k][l][v] + c[i + 1] * 3);
if(K[i + 1] >= 4) chkmin(f[t0][j + 2][k][l][v], f[t][j][k][l][v] + c[i + 1] * 4);
if(K[i + 1] >= 5) chkmin(f[t0][j][k][l + 1][v], f[t][j][k][l][v] + c[i + 1] * 5);
if(K[i + 1] >= 6) chkmin(f[t0][j + 1][k + 1][l][v], f[t][j][k][l][v] + c[i + 1] * 6);
if(K[i + 1] >= 7) chkmin(f[t0][j][k][l][v + 1], f[t][j][k][l][v] + c[i + 1] * 7);
if(K[i + 1] >= 8) chkmin(f[t0][j + 3][k][l][v], f[t][j][k][l][v] + c[i + 1] * 8);
if(K[i + 1] >= 9) chkmin(f[t0][j][k + 2][l][v], f[t][j][k][l][v] + c[i + 1] * 9);
if(K[i + 1] >= 10) chkmin(f[t0][j + 1][k][l + 1][v], f[t][j][k][l][v] + c[i + 1] * 10);
}
}
}
cout << ans << endl;
return 0;
}

遗失的答案

妙妙题..

首先判掉\(L\)不是\(G\)的倍数的情况.

然后先来考虑一下没有一定要包含\(X\)的这个限制的情况:

对于\(L\)的每个质因子\(p_i\),设\(\text{MxP}(p_i,x)=k(p_i^k\mid x,p_i^{k+1}\not\mid x)\);

\(m\)\(L\)不同的质因子的个数.

我就是要选出来一些数使得对于每个质因子\(p_i\),至少存在一个数\(x\)使得\(\text{MxP}(p_i,x)=\text{MxP}(p_i,L)\), 至少存在一个数\(y\)使得\(\text{MxP}(p_i,x)=\text{MxP}(p_i,G)\).

那么我们把每个数都看成一个长为\(2m\)\(01\)串,记录它对于每一个质因子\(p_i\),是否满足\(\text{MxP}(p_i,x)=\text{MxP}(p_i,L)\), 或满足\(\text{MxP}(p_i,x)=\text{MxP}(p_i,G)\).

那么我们最后就是要找若干个数使得它们或出来是一个长为\(2m\)的全是\(1\)的串.因为\(m \le 8\),这道题就变得可做多了.

然后这个是可以\(\text{FWT}\)的.对于\(X\)的限制,记一个前后缀\(\text{FWT}\)的结果就好了,但是复杂度不太对.

我们可以考虑容斥:

我就是要求找出来一些数使它们或为全集,设:\(f(S)\)表示或出来为\(S\)的方案数, \[ g(S)=\sum_{T\subseteq S}f(T) \] 那么\(g(S)=2^{con(S)}\)(\(con(S)\)\(S\)的子集的个数).然后这个就可以直接子集反演了:

\[ f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T) \] 再考虑一下有\(X\)的限制.就是我们或出来的只能是\(X\)的超集.设\(f(S)\)表示或出来的数为\(S\)并且一定选中了\(X\)的方案数.这里的\(g(S)\)和上述的含义一样.只是\(g(S)=[X\subseteq S]2^{con(S)-1}\).减一就是我们去掉没选\(X\)的这种情况.然后容斥和上面是一样的.

虽然询问有很多但是不同的\(01\)状态只有\(2^{2m}\),并且我们每次容斥时只用枚举\(X\)的超集就好了,所以复杂度为\(O(3^{2m})\).(\(m\le 8\))

代码:

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*
* 2257.cpp
* This file is part of 2257
*
* Copyright (C) 2019 - ViXbob
*
* 2257 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2257 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2257. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int n, G, L, Q, x, pow2[maxn], U, l[maxn], r[maxn], siz[maxn], N, ans[1 << 17];
vector<pair<int, int> > facL, data;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void GetFac(int x, vector<pair<int, int> > &fac) {
for(int i = 2; i * i <= x; i++) if(x % i == 0) {
int cnt = 0;
while(x % i == 0) x /= i, cnt++;
fac.pb(mp(i, cnt));
}
if(x != 1) fac.pb(mp(x, 1));
}

inline void Binout(int S) {
stack<int> st;
while(S) st.push(S & 1), S >>= 1;
rep(i, 1, N - st.size()) putchar('0');
while(st.size()) putchar(st.top() + '0'), st.pop();
putchar('\n');
}

inline pair<int, int> GetState(int x) {
int S = 0, y = x;
// cerr << "------------------------" << endl;
// cerr << "x = " << x << endl;
rep(i, 0, SIZE(facL) - 1) {
int cnt = 0;
while(x % facL[i].first == 0) x /= facL[i].first, cnt++;
S |= (cnt == l[i]) << i;
S |= (cnt == r[i]) << i + SIZE(facL);
}
// Binout(S);
return mp(y, S);
}

inline void PreSolve() {
GetFac(L, facL);
pow2[0] = 1; N = SIZE(facL) << 1; U = (1 << N) - 1;
rep(i, 1, U) pow2[i] = pls(pow2[i - 1], pow2[i - 1]);
rep(i, 0, SIZE(facL) - 1) {
r[i] = facL[i].second;
int x = G;
while(x % facL[i].first == 0) l[i]++, x /= facL[i].first;
}
// rep(i, 0, SIZE(facL) - 1) cerr << "l[" << i << "] = " << l[i] << ", r[" << i << "] = " << r[i] << endl;
for(int i = 1; 1ll * i * i <= L; i++) if(L % i == 0) {
if(i % G == 0 && i <= n) data.pb(GetState(i));
if(i * i != L && (L / i) % G == 0 && (L / i) <= n) data.pb(GetState(L / i));
}
sort(data.begin(), data.end());
for(auto v : data) siz[v.second]++;
rep(i, 0, N - 1) rep(S, 0, U) if(S >> i & 1) siz[S] += siz[S ^ (1 << i)];
// rep(S, 0, U) cerr << "size[" << S << "] = " << siz[S] << endl;
}

inline int Solve(int x, int rnt = 0) {
auto it = *lower_bound(data.begin(), data.end(), mp(x, 0));
if(ans[it.second] != -1) return ans[it.second];
int T = it.second, S = U ^ T; rnt = __builtin_popcount(T) & 1 ? dec(rnt, pow2[siz[T] - 1]) : pow2[siz[T] - 1];
for(int S1 = S; S1; S1 = (S1 - 1) & S)
if(__builtin_popcount(S1 | T) & 1) rnt = dec(rnt, pow2[siz[S1 | T] - 1]);
else rnt = pls(rnt, pow2[siz[S1 | T] - 1]);
return ans[it.second] = rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); G = read(); L = read(); Q = read();
if(L % G) { rep(i, 1, Q) puts("0"); return 0; }
PreSolve();
memset(ans, -1, sizeof(ans));
rep(i, 1, Q) {
x = read();
if(x % G != 0 || L % x != 0 || x > n) puts("0");
else printf("%d\n", Solve(x));
}
return 0;
}
/*
2 * 3 * 5
1 2 3 4 5
1
2
2
0
2
*/

魔塔

神仙题答题,不会,告辞.