65 . 隨機演算法 Easy（通靈題）
TopCoder
Tags
Description
喔不，你在「隨機演算法」這門課被當了，但教授表示只要你跟他玩一個隨機的遊戲，你獲勝了就可以通過這門課。
遊戲內容如下：教授會在心中想一個長度為 $65536$ 的陣列 $a$，其中陣列的每個數字只會是 $0$ 或是 $1$。接下來教授會告訴你陣列的內容，並問你 $65536$ 個問題，每次教授會從所有滿足 $0 \leq l \leq r \leq 65535$ 的 $(l, r)$ 中等機率選擇一對並告訴你，而你需要回答教授 $a_l, a_{l + 1}, \ldots, a_r$ 這些數字中 $1$ 的數量是偶數還是奇數。
然而，為了表現出這個課程的內容：隨機。每當你回答了一個問題後，教授會再等機率從 $0$ 到 $65535$ 選一個整數 $i$，並將 $a_i$ 變為 $1 - a_i$。在修改後，對於後續的問題你都必須要針對改變後的陣列回答出正確的答案！
教授也覺得這個遊戲太過困難，所以跟你說你只要回答正確 $32768$ 個問題就算獲勝了。你能戰勝隨機嗎？
Input Format
輸入第一行有 $65536$ 個數字 $a_0, a_1, \ldots, a_{65535}$，其中 $a_i$ 代表一開始陣列第 $i$ 項的值。
接下來 $65536$ 行，每行會給定兩個整數 $b_i, c_i$，請使用以下方法還原出正確的 $l_i, r_i$：
- 定義 $ans_j$ 為第 $i - j$ 筆詢問的正確答案。若 $i - j \leq 0$ 則 $ans_j = 0$。
- 令 $x = \sum\limits_{j = 1}^ {16}ans_j \times 2^ {j - 1}$。
- 則 $l_i = b_i \oplus x, r_i = c_i \oplus x$，其中 $\oplus$ 為 xor operation。
還原出 $l_i, r_i$ 後，在這筆詢問你必須要回答區間 $[l_i, r_i]$ 內 $1$ 的數量為奇數還是偶數。
- $0 \leq a_i \leq 1$
- $0 \leq b_i, c_i \leq 65535$
- 解密後，$0 \leq l_i \leq r_i \leq 65535$
- 每對 $l_i, r_i$ 皆為隨機生成的
Output Format
請輸出 $65536$ 行，若第 $i$ 筆詢問的答案為奇數，請在第 $i$ 行輸出 $1$，否則請在第 $i$ 行輸出 $0$。
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 無其他限制 | 100 |