当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
3606：Sheryl's Circuit II
题目描述
After graduating from college, Sheryl intents to use her circuit to make money. (If you are not familiar with Sheryl’s circuit, turn to Problem 3605 for reference.) She attempts to develop her circuit into a periodic clock generator. The first thing Sheryl wants to know is how many rising edges and falling edges exist in the signal produced when the INPUT goes continuously from all 0s to all 1s. ((0, 0, 0... 0, 0) -> (0, 0, 0... 0, 1) -> (0, 0, 0... 1, 0) -> (0, 0, 0... 1, 1) -> ... -> (1, 1, 1... 1, 0) -> (1, 1, 1... 1, 1))
Figure 1
Consider the circuit showed in Figure 1, when the INPUT goes continuously from (0, 0, 0, 0) to (1, 1, 1, 1), the signal produced by the circuit is the sequence (0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1) which consists of 3 rising edges and 2 falling edges respectively.
Given Sheryl's circuit, your task is to calculate the number of rising edges and the number of falling edges. Since the answers might be very large, you are only required to output the numbers modulo 9973.
输入解释
There are multiple test cases.
The first line contains the number of test cases.
Each test case begins with an integer N( ≤ 10000), the number of inputs of Sheryl's circuit. It is guaranteed that N equals 2k, where k is an integer.
Next N - 1 numbers describe the types of the BAUs, 0 for ∨ and 1 for ∧. The describing order is from top level to bottom level. For the same level it is from left to right.
输出解释
For each test case output the number of rising edges and the number of falling edges modulo 9973 in a separate line.
输入样例
1 4 1 0 1
输出样例
3 2
最后修改于 2020-10-29T07:05:58+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 1000 | 65536 |