g056. 超級加法測試 - 高中生程式解題系統

內容

貓咪要從小一升到小二了，老師在課堂上教了加法，一開始老師會給 $N$ 個數字 $a_{0} \sim a_{N - 1} (0 \leq a_{i} < 998244353)$ ，貓咪要做的就是把他們以以下形式加起來：

$c_{k} = \sum_{x \subseteq k} a_{x} (mod 998244353)$ ， $x \subseteq k$ 代表 $x & k = x$ ，其中 $&$ 是 $bitwise and$ 。

這樣可以得到 $N$ 個數字 $c_{0} \sim c_{N - 1}$ 。貓咪在算好 $c_{0} \sim c_{N - 1}$ 後不小心打翻了墨水，把 $a_{0} \sim a_{N - 1}$ 都塗黑了，給你 $c_{0} \sim c_{N - 1}$ ，你能幫貓咪算出 $a_{0} \sim a_{N - 1}$ 嗎？

輸入說明

輸入只有一行，有三個數字 $N, c_{0}, t$ 。

你要利用 $c_{0}$ 和 $t$ 生成出 $c_{1} \sim c_{N - 1}$ ：

$c_{i} = 10007 \times c_{i - 1} + t (mod 998244353)$

$N = 2^{k} ， 2^{0} \leq N \leq 2^{20}$
$0 \leq c_{0}, t < 998244353$

輸出說明

輸出一個數字 $X$ ，其中 $X = a_{0} xor a_{1} xor . . . xor a_{N - 1}$

範例輸入 #1

8 10 5

範例輸出 #1

846307968

範例輸入 #2

1048576 0 0

範例輸出 #2

範例輸入 #3

1048576 0 1

範例輸出 #3

587805620

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (5%): 2.0s , <1K
不公開測資點#1 (5%): 2.0s , <1K
不公開測資點#2 (5%): 2.0s , <1K
不公開測資點#3 (5%): 2.0s , <1K
不公開測資點#4 (5%): 2.0s , <1K
不公開測資點#5 (5%): 2.0s , <1K
不公開測資點#6 (5%): 2.0s , <1K
不公開測資點#7 (5%): 2.0s , <1K
不公開測資點#8 (5%): 2.0s , <1K
不公開測資點#9 (5%): 2.0s , <1K
不公開測資點#10 (5%): 2.0s , <1K
不公開測資點#11 (5%): 2.0s , <1K
不公開測資點#12 (5%): 2.0s , <1K
不公開測資點#13 (5%): 2.0s , <1K
不公開測資點#14 (5%): 2.0s , <1K
不公開測資點#15 (5%): 2.0s , <1K
不公開測資點#16 (5%): 2.0s , <1K
不公開測資點#17 (5%): 2.0s , <1K
不公開測資點#18 (5%): 2.0s , <1K
不公開測資點#19 (5%): 2.0s , <1K

提示：

由於生測資的時候出現意外，每一行數字最後面都沒有空格。

在範例一， $a_{0} \sim a_{N - 1} = 10, 100065, 3206167, 137087706, 392432960, 589157411, 656220470, 688913139$ 。

$c_{0} \equiv a_{0} \equiv 10$
$c_{1} \equiv a_{0} + a_{1} \equiv 100075 \equiv 10007 \times c_{0} + 5$
$c_{2} \equiv a_{0} + a_{2} \equiv 3206177 \equiv 10007 \times c_{1} + 5$
$c_{3} \equiv a_{0} + a_{1} + a_{2} + a_{3} \equiv 140393948 \equiv 10007 \times c_{2} + 5$
$c_{4} \equiv a_{0} + a_{4} \equiv 392432970 \equiv 10007 \times c_{3} + 5$
$c_{5} \equiv a_{0} + a_{1} + a_{4} + a_{5} \equiv 981690446 \equiv 10007 \times c_{4} + 5$
$c_{6} \equiv a_{0} + a_{2} + a_{4} + a_{6} \equiv 53615254 \equiv 10007 \times c_{5} + 5$
$c_{7} \equiv a_{0} + a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} + a_{7} \equiv 470629222 \equiv 10007 \times c_{6} + 5$

$a_{0} xor a_{1} xor a_{2} xor a_{3} xor a_{4} xor a_{5} xor a_{6} xor a_{7} = 846307968$ 。

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

$100 % ：無特別限制$

標籤:

DP SOS 數學

出處:

[管理者：

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
30407	fire5386 (becaidorz)	g056	SOS DP	577	2022-05-19 17:32