250525-250616
250525 模拟赛 T2 题解
题意
给定一张无向图，包含 \(n\) 个点和 \(m\) 条边（可能包含重边自环），边有边权。有 \(q\) 次询问，每次询问给定 \(x,y,d\)，询问 \(x\) 和 \(y\) 之间是否存在一条路径（可以经过同一个点或边多次），其长度为 \(d\) 的整数倍。输出 Yes 或 No。
\(n,m\le 10^6,\ w\le 2^{60}-1\)
部分分：保证所有边权等于 \(1\)，所有询问 \(d=2\)。
题解
当 \(x\) 和 \(y\) 不在同一个连通块时，答案显然为 No。现在我们考虑同一个连通块中的情况。
考虑部分分。注意到如果连通块内存在奇环，则我们可以随意改变路径的奇偶性，因此这种情况答案一定是 Yes。否则，图是一个二分图，我们只需要判断 \(x,y\) 是否在图的同一侧即可。
考虑普通情况。继续观察，容易发现当 \(d\) 是奇数时，我们只需要找到 \(x\to y\) 的一条路径，然后在路径上走 \(d\) 次即可。
考虑推广这个结论：容易发现，这本质上是把一段长度为 \(l\) 的路径乘上了任意的奇数 \(p\)（上面 \(p=d\)），并且过程是充要的。因此我们可以把 \(d\) 拆分成 \(l\times p\)，取 \(l=2^k\)，\(k\) 即 \(d\) 中质因子 \(2\) 的次数。这样，问题就转化为找到一条被 \(d=2^k\) 整除的路径。
仍然先考虑有奇环的情况。由于边权边权不一定 \(=1\)，此处的奇环定义为权值和为奇数的环。由于一个奇数一定和 \(2^k\) 互质，因此我们可以通过这个环构造出 \(1\pmod {2^k}\)，由此可以直接构造出答案。
否则，图是一个二分图：奇数边跨过两个集合，偶数边两个端点都在同一个集合内。若 \(x,y\) 分布在两个集合中，那么所有 \(x\to y\) 的路径权值和都是奇数，一定不行。若 \(x,y\) 位于同一个集合内，我们先随便找出一条 \(x\to y\) 的路径，路径包含至少一条奇数边，权值和为 \(s\)（有 \(2\mid s\)）。任选路径中一条奇数边，记其权值为 \(w\)，我们希望找到一个满足 \(s+2qw\equiv 0\pmod {2^k}\) 的正整数 \(q\)。注意到这个式子等价于 \(\frac{s}{2}+qw\equiv 0\pmod {2^{k-1}}\)，显然有解（\(w\) 与 \(2^{k-1}\) 互质）。
然而，我们假设了图中存在一条奇数边，这不一定成立。这时，我们可以取连通块中所有边权的 \(\operatorname{gcd}\)，记其中 \(2\) 的次数为 \(p_2\)。如果 \(k\le p_2\)，显然有解；否则我们将所有边权都除以 \(2^{p_2}\)，这样至少会产生一条奇数边，就转换为上面的情况。
代码
| #include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
int v, w, next;
} pool[2 * N];
int ne, head[N];
void addEdge(int u, int v, int w) {
pool[++ne] = {v, w, head[u]};
head[u] = ne;
}
int n, m, q, o;
int nn;
int col[N], scol[N], ok[N], p2[N];
void dfs1(int u) {
col[u] = nn;
for(int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v, w = pool[i].w;
if(w) p2[nn] = min(p2[nn], w & -w);
if(!col[v]) dfs1(v);
}
}
void dfs2(int u) {
if(!scol[u]) scol[u] = 1;
for(int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v, w = pool[i].w;
w /= p2[col[u]];
if(w & 1) {
if(scol[v] && scol[v] == scol[u]) ok[col[u]] = 1;
if(!scol[v]) {
scol[v] = 3 - scol[u];
dfs2(v);
}
} else {
if(scol[v] && scol[v] != scol[u]) ok[col[u]] = 1;
if(!scol[v]) {
scol[v] = scol[u];
dfs2(v);
}
}
}
}
int col0[N], nn0;
void dfs0(int u) {
col0[u] = nn0;
for(int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v, w = pool[i].w;
if(w) continue;
if(col0[v]) continue;
dfs0(v);
}
}
signed main() {
cin >> n >> m >> q >> o;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, w);
}
for(int i = 1; i <= n; i++) p2[i] = INF;
for(int i = 1; i <= n; i++) {
if(!col[i]) {
++nn;
dfs1(i);
if(p2[nn] == INF) p2[nn] = 1;
// cerr << p2[nn] << endl;
dfs2(i);
}
if(!col0[i]) {
++nn0;
dfs0(i);
}
}
#define NO { cout << "villea\n"; continue; }
#define YES { cout << "bougain\n"; continue; }
while(q--) {
int u, v, w;
cin >> u >> v >> w;
if(w == 0) {
if(col0[u] == col0[v]) YES
else NO
}
w = w & -w;
if(col[u] != col[v]) NO
if(ok[col[u]]) YES
if(w <= p2[col[u]]) YES
if(scol[u] == scol[v]) YES
NO
}
return 0;
}
|
250602 模拟赛 T1 题解
题意
给定一棵 \(n\) 个节点的无根树，边有边权。记 \(dis(u,v)\) 表示 \(u\) 和 \(v\) 在树上的距离，\(f(x,u,v)\) 表示 \(u,v\) 简单路径上离 \(x\) 最近的一个点到 \(v\) 的距离。
给定常数 \(k\)，求有多少有序对 \((u,v)\) 满足
\[
\frac 1n\sum_{x=1}^nf(x,u,v)\ge \frac 12 dis(u,v)+k
\]
其中 \(n\le 10^6\)
题解
在固定 \(u,v\) 的情况下，记 \(y_x\) 表示 \(u,v\) 简单路径上离 \(x\) 最近的一个点。我们将题目给定的约束中不够直观、复杂的东西变形，得到：
\[
2\sum_{x=1}^{n}dis(y_x,v)\ge n\times dis(u,v)+2nk
\]
注意到 \(\sum dis(y_x,v)\) 是路径上每个节点挂的子树大小的加权和，比较容易计算；这里可以使用点分治做到 \(O(n\log^2n)\)，获得 \(75pts\)。
我们发现，直接通过这个式子似乎无法获得更低的时间复杂度。因此尝试继续变形：
\[
\begin{align*}
\sum_{x=1}^n2dis(y_x,v)-dis(u,v)\ge&\ 2nk\\
\sum_{x=1}^ndis(y_x,v)-dis(y_x,u)\ge &\ 2nk\\
\end{align*}
\]
式子的形式似乎又变好了一点，但是没有产生任何本质的变化。注意到 \(y_x\) 会让式子变得难以计算，因为它和 \(u,v,x\) 同时有关。注意到我们可以加上 \(dis(x,y_x)\) 再减去 \(dis(x,y_x)\)：
\[
\begin{align*}
\sum_{x=1}^n dis(x,v)-dis(x,u)\ge&\ 2nk\\
\sum_{x=1}^n dis(x,v)-\sum_{x=1}^n dis(x,u)\ge&\ 2nk
\end{align*}
\]
其中 \(\sum dis(x,u)\) 是只和 \(u\) 有关的常量。我们先求出所有 \(s_u=\sum dis(x,u)\)，排序后双指针即可做到 \(O(n\log n)\)。
代码
| #include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
struct Edge {
int v, w, next;
} pool[2 * N];
int ne, head[N];
void addEdge(int u, int v, int w) {
pool[++ne] = {v, w, head[u]};
head[u] = ne;
}
int T;
int n, k;
ll ans;
void clear() {
for(int i = 1; i <= n; i++) head[i] = 0;
ne = 0;
ans = 0;
}
ll sz[N], sum[N];
ll dfs1(int u, int fa) {
ll res = 0;
sz[u] = 1;
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v, w = pool[e].w;
if(v == fa) continue;
res += dfs1(v, u);
sz[u] += sz[v];
res += sz[v] * w;
}
return res;
}
void dfs2(int u, int fa) {
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v, w = pool[e].w;
if(v == fa) continue;
sum[v] = sum[u] + (n - 2 * sz[v]) * w;
dfs2(v, u);
}
}
int main() {
cin >> T;
while(T--) {
cin >> n >> k;
clear();
for(int i = 1; i <= n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, w);
}
sum[1] = dfs1(1, 0);
dfs2(1, 0);
sort(sum + 1, sum + 1 + n);
for(int i = 1, j = 1; i <= n; i++) {
while(sum[i] - sum[j + 1] >= 2ll * n * k) ++j;
if(sum[i] - sum[j] >= 2ll * n * k) {
ans += j;
}
}
cout << ans << '\n';
}
return 0;
}
|
题意
初始有一个长为 \(n\) 的排列，满足 \(a_i=i\)。称另一个排列 \(p\) 是合法的当且仅当它可以由 \(a\) 经过 \(n\) 次操作得到；在第 \(i\) 次操作时，你可以选择一下三种的任意一种执行：
- 找到数字 \(n-i+1\) 在 \(p\) 中出现的位置 \(j\)，若 \(j\ne 1\)，你可以交换 \(p_j\) 和 \(p_{j-1}\)；
- 找到数字 \(n-i+1\) 在 \(p\) 中出现的位置 \(j\)，若 \(j\ne n\)，你可以交换 \(p_j\) 和 \(p_{j+1}\)；
- 什么都不做；
有 \(q\) 次询问，每次询问给定 \(n,k\)，问所有合法的排列中字典序第 \(k\) 小的排列是什么。
\(\sum{n}\le 2\times 10^5,\ k\le 10^{18}\)
题解
考虑试填法，我们需要知道当前位置可以填哪些字符，以及对应的方案数。通过手玩数据我们能发现 \(p\) 中数字 \(1\) 出现的位置不会太靠后，只能位于 \(p_1,p_2,p_3\)。写出三种情况：
由于第二种情况第一个位置的 ? 让我们不能直接判断三种情况的字典序。因此继续分讨：
其中 \(x>2\)。注意到，? 部分经过偏移之后可以形成一个子问题。
先考虑计数，设 \(f_{0,n}\) 表示长为 \(n\) 的合法排列数量，\(f_{1,n}\) 表示长为 \(n\) 且第一位是 \(1\) 的合法排列数量。根据子问题转化的性质，我们可以写出转移：
\[
\begin{align*}
f_{0,n}=f_{0,n-1}+2f_{0,n-2}+(f_{0,n-1}-f_{1,n-1})\\
f_{1,n}=f_{0,n-1}
\end{align*}
\]
显然可以简化成一个维度的式子：
\[
f_{n}=2f_{n-1}+f_{n-2}
\]
这样，我们通过 \(O(n)\) 的预处理就可以解决计数的问题。试填的时候我们记一个 tag 表示当前子问题的第一个位置能不能填 \(1\) 即可。
代码
| #include<iostream>
#include<cassert>
#define int long long
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int INF2 = 1e18;
int T;
int n, k;
int f[N];
void dfs(int n, int k, int b, int res[], bool tag = 0) {
if(n == 0) {
assert(k == 1);
return;
}
if(n == 1) {
assert(k == 1);
res[1] = 1 + b;
return;
}
if(!tag && k <= f[n - 1]) {
res[1] = 1 + b;
dfs(n - 1, k, b + 1, res + 1);
return;
} else if(!tag) k -= f[n - 1];
if(k <= f[n - 2]) {
res[1] = 2 + b;
res[2] = 1 + b;
dfs(n - 2, k, b + 2, res + 2);
return;
} else k -= f[n - 2];
assert(n - 2 > 0);
if(k <= f[n - 2]) {
res[1] = 2 + b;
res[2] = 1 + b;
dfs(n - 2, k, b + 2, res + 2);
swap(res[2], res[3]);
return;
} else k -= f[n - 2];
if(k <= f[n - 1] - f[n - 2]) {
res[1] = 1 + b;
dfs(n - 1, k, b + 1, res + 1, 1);
swap(res[1], res[2]);
return;
}
throw;
}
int res[N];
signed main() {
f[1] = 1;
for(int i = 2; i < N; i++) {
if(f[i - 1] >= INF2) f[i] = INF;
else f[i] = 2 * f[i - 1] + f[i - 2];
}
f[0] = 1;
cin >> T;
while(T--) {
cin >> n >> k;
if(k > f[n]) { cout << "-1\n"; continue; }
dfs(n, k, 0, res);
for(int i = 1; i <= n; i++) {
cout << res[i] << ' ';
}
cout << '\n';
}
return 0;
}
|
250610 模拟赛 T2 题解
题意
给定一棵 \(n\) 个点，以 \(1\) 为根的有根树，第 \(i\) 个点的点权初始为 \(a_i\)。你需要进行 \(q\) 次修改，每次修改给定两个点 \(x,y\)，表示交换 \(a_x,a_y\)。你需要在每次操作之后回答一个问题：
记 \(S_u\) 表示 \(u\) 子树内所有点的点权组成的序列，从小到大排好序的结果。记所有 \(S_u\) 中字典序最小的一个为 \(L\)，问 \(\sum{[S_u=L]u}\)。
\(n,q\le 2\times 10^5,\ a_i\le 10^9\)
题解
首先注意，\(L\) 肯定是 \(S_1\) 的一个前缀。并且，当且仅当存在一个叶子节点的权值等于 \(1\) 时，\(L=[1]\)；其余情况 \(S_u=L\) 的 \(u\) 有且仅有一个。先特判掉叶子的情况。
考虑一个节点 \(u\) 成为答案的条件。容易发现，因为我们只有交换操作，所以 \(S_1\) 是不会改变的。又因为 \(L\) 必须是 \(S_1\) 的前缀，而且 \(L\) 的长度等于答案节点的子树大小，因此一个节点 \(u\) 成为答案当且仅当 \(S_u=S_1[1\sim sz_u]\)。记 \(T_u=S_1[1\sim sz_u]\)。
考虑 \(S_u\) 和 \(T_u\) 匹配的情形：
S[u]: 1 1 1 1 2 2 2 3 3 3 3 4 4 4
T[u]: [ 1 1 1 1 2 2 2 3 3 3 3 4 4 4 ] 4 4 4 5 5 5 5 ...
而不匹配的情形：
1-4 的数量太少
S[u]: 1 1 1 1 2 2 3 3 4 5 5 ...
T[u]: [ 1 1 1 1 2 2 2 3 3 3 3 4 4 4 ] 4 4 4 5 5 5 5 ...
4 太多
S[u]: 1 1 1 1 2 2 2 3 4 4 4 4 4 4
T[u]: [ 1 1 1 1 2 2 2 3 3 3 3 4 4 4 ] 4 4 4 5 5 5 5 ...
\(T_u\) 形如值域上一段前缀，再加上下一个数的一段。记 \(sc[i]\) 表示（离散化之后）\(S_1\) 中小于等于 \(i\) 的数字的数量，\(ac[u]\) 表示最大的满足 \(sc[i]<sz[u]\) 的颜色 \(i\)。例子中，\(ac[i]=3\)。
匹配时，子树内 \(\le ac\) 的数字数量等于 \(sc[ac]\)，并且 \(ac+1\) 的数量等于 \(sz[u]-sc[ac]\)。然而，两个维度的信息较难维护，尝试将它们合并成一维。注意到 \(cnt(ac+1)\) 比 \(sz[u]-sc[ac]\) 可大可小，却不会超过 \(sz[u]-cnt(\le ac)\)。即：
\[
\begin{cases}
cnt(\le ac)\le sc[ac]\\
cnt(ac+1)\le sz[u]-cnt(\le ac)
\end{cases}
\]
并且在匹配时，两个不等号同时取等。这启发我们维护
\[
sc[ac]+sz[u]-2cnt(\le ac)-cnt(ac+1)
\]
因为它始终大于等于 \(0\)，并且在匹配时取等。
同时我们注意到，在一条根链上随着深度的减小，\(sz\) 单调递增，因此对应的 \(ac\) 也单调递增。对于节点 \(i\) 处的数字 \(a_i\)，它会在根链的两个连续区间上分别产生 \(-1,-2\) 的贡献，区间的位置可以使用倍增求得。然后用树剖维护上面的式子，每次修改时进行区间加减，然后查询最小值 \(0\) 出现的位置即可。
不等式可加性
将题目需要的取等关系放在恒成立的不等式中，然后将不等式左右两边分别相加再作差，可以将多个式子压为一个式子。
代码
| #include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
const int N = 2e5 + 10;
const int LOGN = 19;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, next;
} pool[2 * N];
int ne, head[N];
void addEdge(int u, int v) {
pool[++ne] = {v, head[u]};
head[u] = ne;
}
int n, q;
int a[N];
int num[N], scnt[N], nn;
void lisanhua() {
for(int i = 1; i <= n; i++) num[++nn] = a[i];
sort(num + 1, num + 1 + nn);
nn = unique(num + 1, num + 1 + nn) - (num + 1);
for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}
int dfn[N], id[N], dt;
int sz[N], fa[N], son[N], top[N];
int c[N], ac[N] = {INF}; // sz+a0; 最后一个 scnt< sz 的颜色
bool isleaf[N];
int sl;
int anc[LOGN][N];
namespace SegT {
struct myPair {
int val, pos;
inline myPair() { val = pos = 0; }
inline myPair(int _1, int _2) : val(_1), pos(_2) {}
inline myPair &operator+=(int x) {
val += x;
return *this;
}
inline bool operator<(const myPair &b) const {
if(val != b.val) return val < b.val;
return sz[pos] < sz[b.pos];
}
};
myPair mn[4 * N];
int tag[4 * N];
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
inline void push_up(int p) {
mn[p] = min(mn[lc(p)], mn[rc(p)]);
}
inline void move_tag(int p, int tg) {
tag[p] += tg;
mn[p] += tg;
}
inline void push_down(int p) {
if(!tag[p]) return;
move_tag(lc(p), tag[p]);
move_tag(rc(p), tag[p]);
tag[p] = 0;
}
void build(int p, int l, int r) {
if(l == r) {
mn[p] = {c[id[l]], id[l]};
return;
}
int mid = (l + r) >> 1;
build(lc(p), l, mid);
build(rc(p), mid + 1, r);
push_up(p);
}
void add(int p, int l, int r, int ql, int qr, int v) {
if(ql <= l && r <= qr) {
move_tag(p, v);
return;
}
push_down(p);
int mid = (l + r) >> 1;
if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
push_up(p);
}
inline int query() {
assert(mn[1].val == 0);
return mn[1].pos;
}
}
void dfs1(int u) {
sz[u] = 1;
anc[0][u] = fa[u];
for(int k = 1; k < LOGN; k++) {
anc[k][u] = anc[k - 1][ anc[k - 1][u] ];
}
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(v == fa[u]) continue;
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
ac[u] = lower_bound(scnt + 1, scnt + 1 + nn, sz[u]) - scnt - 1;
c[u] = scnt[ac[u]] + sz[u];
if(!pool[head[u]].next) isleaf[u] = 1;
}
void dfs2(int u, int tp) {
dfn[u] = ++dt;
id[dt] = u;
top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline void add_path(int p, int v) {
while(p) {
SegT::add(1, 1, n, dfn[top[p]], dfn[p], v);
p = fa[top[p]];
}
}
inline void insert(int p, int v, int w = 1) {
int bg = p;
if(isleaf[p] && v == 1) sl += w * p;
for(int k = LOGN - 1; k >= 0; k--) {
if(ac[anc[k][p]] + 1 < v) p = anc[k][p];
}
if(ac[p] + 1 < v) p = fa[p];
if(!p) return;
add_path(p, -w);
for(int k = LOGN - 1; k >= 0; k--) {
if(ac[anc[k][p]] < v) p = anc[k][p];
}
if(ac[p] < v) p = fa[p];
if(!p) return;
add_path(p, -w);
}
inline void modify(int x, int y) {
insert(x, a[x], -1);
insert(y, a[y], -1);
swap(a[x], a[y]);
insert(x, a[x], 1);
insert(y, a[y], 1);
}
inline int query() { return SegT::query(); }
int main() {
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
lisanhua();
for(int i = 1; i <= n; i++) ++scnt[a[i]];
for(int i = 1; i <= nn; i++) scnt[i] += scnt[i - 1];
dfs1(1);
dfs2(1, 1);
SegT::build(1, 1, n);
for(int i = 1; i <= n; i++) insert(i, a[i]);
while(q--) {
int x, y;
cin >> x >> y;
modify(x, y);
if(sl) cout << sl << '\n';
else cout << query() << '\n';
}
return 0;
}
|
250616 模拟赛 T1 题解
题意
给定一个二分图，包含 \(n_1\) 个左部点和 \(n_2\) 个右部点，以及最多 \(n_1n_2\) 条边。称一个点集 \(S\) 是合法的当且仅当存在原图的一个匹配，使得 \(S\) 中的每个点都连接了一条匹配边。
给定二分图每个点的点权 \(c_i\)，有 \(q\) 次询问，每次询问给定 \(k\)，询问合法且异或和为 \(k\) 的点集 \(S\) 的数量。
\(n_1,n_2\le 20,\ 0\le c_i< 2^20\)
题解
考虑 \(S\) 合法的一个必要条件：\(S\) 左边和右边的点分别满足霍尔定理。
记 \(S_1\) 为 \(S\) 在左边的点，\(S_2\) 为 \(S\) 在右边的点，即必须存在 \(S_1\) 向 \(V_2\)（全体右部点）的完美匹配 \(E_1\) 和 \(S_2\) 向 \(V_1\)（全体左部点）的完美匹配 \(E_2\)。
稍微手玩一下发现这个条件特别充分，于是尝试证明这一点。为了方便叙述，我们将匹配边定向，记 \(x_u\) 表示左部点 \(u\) 在右边的匹配点，\(y_v\) 同理。由于每个点的入度和出度都不超过 \(1\)，因此图中形如一些链和偶环，不难发现二者都是容易调整的。
我们只需要预处理出左边和右边满足霍尔定理的子集，异或卷积即可。
但是 \(O(3^n)\) 的预处理不能通过本题。考虑集合 \(S\)，它的任意一个子集要么是它本身，要么是 \(|S|\) 个 \(S/\{x\}\) 的一个子集。这里的枚举量是 \(O(n2^n)\) 的，可以接受。
代码
| #include<bits/stl_algobase.h>
#include<cstdio>
#include<cmath>
#include<unistd.h>
#include<ctype.h>
#include<string>
#include<cassert>
#define ll long long
using namespace std;
const int N = 20;
const int MOD = 1e9 + 7;
struct istream {
char ch;
template<typename _Tp>
inline istream &operator>>(_Tp &x) {
while(!isdigit(ch = getchar_unlocked()));
x = ch - '0';
while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
return *this;
}
} cin;
struct ostream {
char buf[60], top;
inline ostream() : top(0) {}
inline ostream &operator<<(char c) {
putchar_unlocked(c);
return *this;
}
inline ostream &operator<<(const string& s) {
for(int i = 0; i < s.size(); i++) putchar_unlocked(s[i]);
return *this;
}
inline ostream &operator<<(int x) {
do buf[++top] = x % 10, x /= 10; while(x);
while(top) putchar_unlocked(buf[top--] + '0');
return *this;
}
} cout;
int n, m, e, q;
int cnt[1 << N];
int to[2][1 << N];
bool ok[2][1 << N];
int sum[2][1 << N], f[3][1 << N];
int lg[1 << N];
void FWT(int a[]) {
for(int k = 1; k < 1048576; k <<= 1) {
int k2 = k << 1;
for(int i = 0; i < 1048576; i += k2) {
for(int j = 0; j < k; j++) {
assert(i + j + k < 1048576);
int x = a[i + j], y = a[i + j + k];
a[i + j] = (x + y) % MOD;
a[i + j + k] = ((ll)x - y + MOD) % MOD;
}
}
}
}
void iFWT(int a[]) {
for(int k = 1; k < 1048576; k <<= 1) {
int k2 = k << 1;
for(int i = 0; i < 1048576; i += k2) {
for(int j = 0; j < k; j++) {
assert(i + j + k < 1048576);
int x = (ll)a[i + j] * 500000004 % MOD, y = (ll)a[i + j + k] * 500000004 % MOD;
a[i + j] = (x + y) % MOD;
a[i + j + k] = ((ll)x - y + MOD) % MOD;
}
}
}
}
int a[N], b[N];
// #define FIO
int main() {
#ifdef FIO
freopen("bip.in", "r", stdin);
freopen("bip.out", "w", stdout);
#endif
cin >> n >> n >> m >> e >> q;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < m; i++) cin >> b[i];
for(int i = 1; i <= e; i++) {
int u, v;
cin >> u >> v;
--u, --v;
to[0][1 << u] |= (1 << v);
to[1][1 << v] |= (1 << u);
}
for(int i = 1; i < (1 << max(n, m)); i++) cnt[i] = cnt[i ^ (i & -i)] + 1;
for(int i = 2; i < (1 << max(n, m)); i++) lg[i] = lg[i >> 1] + 1;
ok[0][0] = ok[1][0] = 1;
for(int i = 1; i < (1 << n); i++) {
if(i == (i & -i)) { ok[0][i] = cnt[to[0][i]] >= cnt[i]; continue; }
int j = i & -i;
to[0][i] = to[0][i ^ j] | to[0][j];
ok[0][i] = cnt[to[0][i]] >= cnt[i];
}
for(int i = 1; i < (1 << m); i++) {
if(i == (i & -i)) { ok[1][i] = cnt[to[1][i]] >= cnt[i]; continue; }
int j = i & -i;
to[1][i] = to[1][i ^ j] | to[1][j];
ok[1][i] = cnt[to[1][i]] >= cnt[i];
}
for(int i = 1; i < (1 << n); i++) {
for(int j = 0; j < n; j++) {
if(~i & (1 << j)) continue;
ok[0][i] = ok[0][i] && ok[0][i ^ (1 << j)];
}
if(ok[0][i]) sum[0][i] = sum[0][i ^ (i & -i)] ^ a[lg[i & -i]];
}
for(int i = 1; i < (1 << m); i++) {
for(int j = 0; j < m; j++) {
if(~i & (1 << j)) continue;
ok[1][i] = ok[1][i] && ok[1][i ^ (1 << j)];
}
if(ok[1][i]) sum[1][i] = sum[1][i ^ (i & -i)] ^ b[lg[i & -i]];
}
for(int i = 0; i < (1 << n); i++) if(ok[0][i]) ++f[0][sum[0][i]];
for(int i = 0; i < (1 << m); i++) if(ok[1][i]) ++f[1][sum[1][i]];
FWT(f[0]);
FWT(f[1]);
for(int i = 0; i < (1 << 20); i++) f[2][i] = (ll)f[0][i] * f[1][i] % MOD;
iFWT(f[2]);
while(q--) {
int x;
cin >> x;
cout << f[2][x] << '\n';
}
return 0;
}
|