A16723 | $Mosaic Tree$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

大师制作了一幅由 $n$ 个彩色马赛克元素组成的作品。每个元素被涂成 $m$ 种可能颜色中的一种（颜色编号为 $1$ 到 $m$）。 大师将作品排列成能够表示为一棵树的形式。 如果对于每种颜色 $i$，所有颜色为 $i$ 的顶点的度数之和具有指定的奇偶性 $\mathrm{mask}_i$，则称该作品是美丽的，其中 $\mathrm{mask}$ 是包含 $m$ 个 $0$ 或 $1$ 的数组。 请帮助大师计算有多少种方法可以制作一幅美丽的作品。请将答案对 $10^9 + 7$ 取模后输出。

每个测试点包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^4$），分别表示顶点数量和可选颜色数量。 第二行包含 $n$ 个整数 $c_i$（$1 \le c_i \le m$），表示第 $i$ 个顶点的颜色。 第三行包含 $m$ 个整数 $\mathrm{mask}_i$（$\mathrm{mask}_i \in \{0, 1\}$），表示第 $i$ 种颜色顶点度数之和的奇偶性要求（若和为偶数，则 $\mathrm{mask}_i = 0$，否则 $\mathrm{mask}_i = 1$）。 保证所有测试用例中 $n$ 之和不超过 $10^4$，$m$ 之和也不超过 $10^4$。

对于每个测试用例，输出一个整数，表示制作美丽作品的方案数，对 $10^9 + 7$ 取模。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出