In the distant land of Bitland, where all things operate based on binary logic, there exists a powerful artifact known as the "Bitstone." For centuries, it has maintained balance and order throughout the kingdom. However, one fateful day, the Bitstone began to lose its power, and chaos spread across the land.
The royal scholars discovered that the artifact's energy, symbolized by a number $$$n$$$, represents the current instability of the Bitstone. The only way to restore balance is to find two magical numbers $$$x$$$ and $$$y$$$ that satisfy the ancient binary laws of Bitland:
1. $$$(x \oplus y) = n$$$
2. $$$(x \& y) = 2n$$$
As a skilled programmer, you have been called upon to find how many such valid pairs $$$(x,y)$$$ exist for a given $$$n$$$ and help restore balance to Bitland before the chaos becomes irreversible.
The first line contains a single integer $$$t(1 \le t \le 10^3)$$$ — the number of test cases.
Each test case contains a single integer $$$n (0 \le n \le 10^{15})$$$ — the imbalance of the Bitstone.
For each test case, output a single integer representing the number of distinct valid pairs $$$(x, y)$$$ that can stabilize the Bitstone and restore peace to the kingdom.
701810121721
1 2 2 4 0 4 8
For $$$n = 0$$$, we need to find pairs $$$(x, y)$$$ such that:
1. $$$(x \oplus y) = 0$$$ (which means $$$x = y$$$)
2. $$$(x \& y) = 0$$$
The only possible solution in this case is $$$(0, 0)$$$ and the answer is $$$1$$$.
For $$$n = 1$$$, we need to find pairs $$$(x, y)$$$ such that:
1. $$$(x \oplus y) = 1$$$ (which means $$$x$$$ and $$$y$$$ must have a bit difference only at the lowest bit.)
2. $$$(x \& y) = 2$$$ (both $$$x$$$ and $$$y$$$ must have a bit set at the second position.)
So, the valid pairs are $$$(2,3)$$$ and $$$(3,2)$$$, and the answer is $$$2$$$.
The most classic instrument in Mexican music is the maraca, which is made up of a handle and a ball on top containing seeds and it functions as a type of rattle. As everyone knows, the use of pairs of maracas is mandatory!
You have just arrived in Mexico and will participate in a maraca circle with exactly $$$N$$$ people. At the $$$i$$$-th position of the circle, there is a number of maracas $$$m_i$$$. Your task is to redistribute the maracas so that each position has an even number of maracas to be used; after all, there cannot be a maraca without its pair. Since the circle is really big, you can only take maracas from a position and move them to the position immediately to the left or right.
The time it takes to carry a maraca from one position to another is directly proportional to the number of maracas being carried, because the greater the quantity, the heavier the weight. The time to carry a maraca to the left is $$$A$$$ seconds, and to the right is $$$B$$$ seconds. Additionally, if you're not carrying any maracas, you can move very quickly between positions (in zero seconds).
Since everyone wants to start making music as soon as possible, your goal is to determine the minimum time needed to complete this task. If it's not possible to achieve the task, you should print $$$-1$$$.
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$).
The second line contains $$$N$$$ integers $$$1 \leq m_i \leq 10^9, \, i = 1,\ldots, N$$$. Note that the list of quantities of maracas is circular, that is, position $$$i$$$ is adjacent to $$$i+1$$$ and position $$$N$$$ is adjacent to position 1.
The third line contains two integers $$$A$$$ and $$$B$$$. $$$1 \leq A, B \leq 10^9$$$
Print a single integer: the minimum time if possible or -1.
11 2 3 4 2 3 3 1 1 9 6 10 1 9
5
6 1 1 1 1 1 3 4 10
12
Yessine was in the middle of an exam when he got bored. He doesn't really like exams or studying, but he likes problem-solving so he unconsciously started thinking about random problems. At that moment , one particular problem came to his mind:
You have to make an $$$n\times n$$$ grid consisting of white cells and black cells. There are only two constraints:
- The number of black cells on the $$$i^\texttt{th}$$$ column is $$$C_i$$$
- The number of black cells on the $$$i^\texttt{th}$$$ row is $$$R_i$$$
Yessine would've loved to solve this problem, but he remembered he was taking an exam and he must answer the questions or he would fail, so he left it to you.
The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.
The first line of each test case contains the integer $$$1\leq n \le 2000$$$
The second line of each test case contains $$$n$$$ space separated integers $$$0\leq C_1,\dots, C_n \leq n$$$
The third line of each test case contains $$$n$$$ space separated integers $$$0\leq R_1,\dots, R_n \leq n$$$
It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$4$$$.$$$10^6$$$
If there exists such $$$n\times n$$$ grid, output any (black cells are represented by 1 and white cells are represented by 0) else output $$$-1$$$
3 4 3 3 3 2 3 4 1 3 3 3 3 1 3 3 2 4 2 2 3 2 2 2 3 2
0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 -1 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0
For the second test case, let's suppose that such $$$3\times 3$$$ matrix $$$A$$$ exists. As $$$R_1=R_2=C_1=C_2=3,$$$ necessarily, we have $$$A=\begin{matrix} 1&1&1\\ 1&1&1\\ 1&1& * \end{matrix}.$$$ This implies that $$$C_3\ge 2,$$$ which is a contradiction as $$$C_3=1.$$$
Therefore, such matrix does not exist.