k301. 老鼠愛 PY - 高中生程式解題系統

內容

有一天老鼠走在路上，看到了 $n$ 隻蟒蛇 (python)，每隻蟒蛇的長度是 $a_{1} \sim a_{n}$ 。

已知長度為 $x$ 的蟒蛇在經過蛻皮後，長度會變成 $x^{- 1} (mod 10^{9} + 7)$ ，也就是 $x$ 在模 $10^{9} + 7$ 下的模逆元 $(x \times x^{- 1} \equiv 1 (mod 10^{9} + 7))$ 。

老鼠想知道這 $n$ 隻蟒蛇在蛻皮後的長度會變成多少，只是他如果算太久，就會被蟒蛇抓走開蟒蛇派對(老鼠會被吃！)，所以請你幫幫他！

只是蟒蛇的數量可能很多，光是輸入輸出可能就會超過時限了，所以請以以下方式得到蟒蛇長度和輸出答案：

輸入會給你四個正整數 $n, a_{1}, m, k$ ，編號 $i (i > 1)$ 蟒蛇的長度 $a_{i} = max (1, (m \times a_{i - 1} + k) mod 10^{9} + 7)$ 。

當你算出每個蟒蛇蛻皮後的長度 $a_{1}^{- 1}, a_{2}^{- 1}, \dots a_{n}^{- 1}$ 後，請輸出 $a_{1}^{- 1} \oplus a_{2}^{- 1} \oplus \dots \oplus a_{n}^{- 1}$ ，其中 $\oplus$ 代表的是 $bitwise xor$ 運算。

輸入說明

輸入一行，有四個正整數 $n, a_{1}, m, k$ ，代表蟒蛇數量、第 $1$ 隻蟒蛇的長度、算式的係數。

$2 \leq n \leq 10^{7}$
$1 \leq a_{1}, m, k < 10^{9} + 7$

輸出說明

輸出一個整數，代表 $a_{1}^{- 1} \oplus a_{2}^{- 1} \oplus \dots \oplus a_{n}^{- 1}$ 。

範例輸入 #1

123 456 789 11111

範例輸出 #1

945184247

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (3%): 1.0s , <1K
不公開測資點#1 (3%): 1.0s , <1K
不公開測資點#2 (4%): 1.0s , <1K
不公開測資點#3 (45%): 1.0s , <1K
不公開測資點#4 (45%): 1.0s , <1K

提示：

你能用 PY 寫出這題嗎？

----------------------------------------------

$10 % ： n \leq 5 \times 10^{5}$

$90 % ：無特別限制$

標籤:

數學

出處:

[管理者：

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」