Sheryl's Circuit II
Description
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.
Input
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.
Output
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 13 2Source
POJ Founder Monthly Contest – 2008.06.29, Dagger