石老板阴阳调和
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
“你自由了!”锟斤拷星人对石老板说。
接着,石老板被飞船抛出,传送到了一个未知的星球上。当石老板回过神来时,发现自己被关入了一间黑暗的密室中。他用最后一根火柴点燃了火把,看到眼前有 个石柱,编号为 。每个石柱上有不同的雕刻,有些石柱上的雕刻是凸出的,称之为“阳”;有些石柱上的雕刻是凹进去的,称之为“阴”。
石老板从壁画中了解到,可以通过点燃墙壁上的火炬改变石柱的阴阳状态。具体来说,一共有 个火炬,第 个火炬如果点燃,可以改变 个石柱的阴阳状态(阴变为阳,阳变为阴),这些石柱的编号为 。只有把所有石柱都变为阴或者都变为阳,才能触发石门的机关,逃出密室。
现在有 种初始的情况,每种情况给出了初始 个石柱的阴阳状态,请你分别求出每种情况下有多少种方案能使得所有石柱都变为阴或者阳。两种方案不同当且仅当存在一个火炬在一种方案中点燃,另一种方案中未点燃,而与火炬点燃的顺序无关。
输入格式
第一行三个整数 ,分别表示石柱的数量、火炬的数量以及初始情况数。
接下来 行,每行第一个整数 ,表示第 个火炬能影响的石柱数量。接着有 个不同的整数 表示每个受影响的石柱编号,用空格分隔。
接下来 行,每行 个整数 ,表示第 个石柱的初始阴阳状态, 表示阴, 表示阳。
输出格式
输出 行,每行一个整数,表示使得所有石柱都变为阴或者阳的方案数对 取模的结果。
样例输入
5 4 3
0
1 1
3 2 3 4
2 4 5
1 1 1 1 1
0 1 1 0 1
0 1 0 0 0
样例输出
2
2
0
样例解释
一共有 个石柱, 个火炬, 种初始状态。
点燃第一个火炬不能改变石柱的状态,点燃第二个火炬可以改变第 个石柱的状态,点燃第三个火炬可以改变第 个石柱的状态,点燃第四个火炬可以改变第 个石柱的状态
第一种情况,不能变为全阴,但有两种方案可以变为全阳:点燃第一个火炬或者都不点燃。
第二种情况,不能变为全阳,但有两种方案可以变为全阴:点燃第 个火炬,或者点燃第 个火炬。
第三种情况,无论怎么操作都不能让石柱变为全阴或者全阳。
数据范围
对于 的数据:。
对于 的数据:。
对于 的数据:,,,。