100 atcoder#ABC128C. [ABC128C] Switches
[ABC128C] Switches
题目描述
on と off の状態を持つ 個の スイッチと、 個の電球があります。スイッチには から の、電球には から の番号がついています。
電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を で割った余りが に等しい時に点灯します。
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
全ての電球が点灯するようなスイッチの on/off の状態の組み合わせの個数を出力せよ。
题目大意
题目描述
有 个开关和 个灯泡,每个开关都处于“开”和“关”状态中的一种。开关从 到 编号,灯泡从 到 编号。
号灯泡连接着 个开关:开关 ,,...,。当这些开关中,处于“开”状态的开关数量之和模 2 余 时,这个灯泡就会被点亮。
有多少“开”和“关”的组合,可以点亮所有灯泡?
输入格式
输入来自以下格式的标准输入:
输出格式
输出一个数,表示有多少总组合方案可以点亮所有灯泡。
说明/提示
数据范围
-
-
-
-
-
只能是 或
-
上述所有值都是整数
样例 1/样例 4
-
灯泡 当以下开关里开着的总数是偶数时会亮:开关 和 。
-
灯泡 当以下开关里开着的总数是奇数是会亮:开关 。
开关 和 一共组成了四种组合:(开,开),(开,关),(关,开)和(关,关)。其中只有(开,开)满足要求,所以输出 。
样例 2/样例 5
-
灯泡 当以下开关里开着的总数是偶数时会亮:开关 和 。
-
灯泡 当以下开关里开着的总数是偶数时会亮:开关 。
-
灯泡 当以下开关里开着的总数是奇数时会亮:开关 。
为了点亮灯泡 ,开关 必须是关着的;为了点亮灯泡 ,开关 必须是开着的。但这样灯泡 就不能被点亮了。所以,没有组合能让所有灯泡亮起来,故输出 。
2 2
2 1 2
1 2
0 1
1
2 3
2 1 2
1 1
1 2
0 0 1
0
5 2
3 1 2 5
2 2 3
1 0
8
提示
制約
- は または
- 入力は全て整数である
Sample Explanation 1
- 電球 は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ - 電球 は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ (スイッチ 、スイッチ ) の状態としては (on,on),(on,off),(off,on),(off,off) が考えられますが、このうち (on,on) のみが条件を満たすので、 を出力してください。
Sample Explanation 2
- 電球 は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ - 電球 は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ - 電球 は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ 電球 を点灯させるためには スイッチ が off, 電球 を点灯させるためにはスイッチ が on である必要がありますが、この時電球 は点灯しません。 よって、全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは存在しないので、 を出力してください。