← 返回题目列表

AtCoder · dwacon6th_final_b

B. 丰收节

中文机器翻译题面 查看原题

配点 : 800 点

問題文

在某个国家,超市每年都会举办丰收节,汇集各个城镇种植的农作物。

在这个国家 有 N 个城镇,每个城镇都有 它的编号为 0, \ldots, N-1 。 另外, 编号为0, \ldots, M-1 它有多个 M 有一条书的路,一条路 i 是一个城镇 x_i 和镇 y_i 是长度 它在两个方向上都与 d_i 连接。 在所有城镇中,数量 a_0, \ldots, a_{K-1} 的 K 城镇有超市。

当年举办丰收节的超市组根据以下条件确定。

  • 各城镇将邀请所有城镇在丰收节上展示物品。 1 已选择多于一项
  • 为了在农作物新鲜时举办活动,距所有选定城镇的最短距离是 在 D 内的一家超市举行
  • 为了在尽可能多的超市举办活动,将在上述所有超市举办。

所有超市合集 A' \subseteq \{ a_0, \ldots, a_{K-1} \} , 当我输入A' 计算选择举办丰收祭的城镇的方法数。 计算除以 998244353 后的余数并输出它们的异或。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq \min \left(N(N-1)/2, 2 \times 10^5 \right)
  • 1 \leq K \leq \min(N, 20)
  • 1 \leq D \leq 10^9
  • 0 \leq a_i \leq N-1
  • a_0, \ldots, a_{K-1} 不同
  • 0 \leq x_i, y_i \leq N-1
  • 1 \leq d_i \leq 10^9
  • 所有输入值均为整数
  • 当考虑以城镇为顶点、以道路为边的无向图时,该图不包含多条边或自环。

入力

输入是按以下格式从标准输入给出的。

N M K D
a_0 a_1 \ldots a_{K-1}
x_0 y_0 d_0
\vdots
x_{M-1} y_{M-1} d_{M-1}

出力

打印答案。


入力例1

3 1 3 1
0 1 2
1 2 1

出力例1

1
  • 若镇 0 超市将举办丰收节。 如果
    • 町 0 出售
  • 若镇 1, 2 超市将举办丰收节。 如果
    • 町 1 出售
    • 町 1, 2 出售
    • 町 2 出售
  • 下列情况,超市不得举办丰收节。
    • 町 0, 1 出售
    • 町 0, 2 出售
    • 町 0, 1, 2 出售

因此, 输出1\ \mathop{XOR}\ 3\ \mathop{XOR}\ 3 = 1 。


入力例2

5 4 3 2
1 2 3
0 1 2
1 2 1
2 3 5
3 4 5

出力例2

17

入力例3

4 2 4 2
0 1 2 3
0 1 1
2 3 1

出力例3

9

入力例4

9 9 4 6
1 3 6 8
1 4 4
6 7 1
4 5 3
3 6 2
4 7 5
7 8 1
1 5 3
1 0 2
4 8 1

出力例4

367