h999. 線上外賣學習 - 高中生程式解題系統

內容

$Waimai$ 的班上有人確診了，於是 $Waimai$ 要居家隔離。

總共要隔離 $n$ 天，每天 $Waimai$ 都可以叫外賣。今天要吃什麼呢？ $Waimai$ 有 $m + 1$ 種選擇，他可以從 $m$ 種食物裡選第 $i$ 種，且飽足度為 $a_{i}$ ，或是可以什麼都不選，飽足度為 $0$ 。

經過 $n$ 天後， $Waimai$ 最後的總飽足度為 $1 \sim n$ 天飽足度的加總。 $Waimai$ 想知道他的總飽足度為 $0 \sim k$ 分別的方法數。假設 $c n t_{i}$ 為讓總飽足度為 $i$ 的方法數對 $998244353$ 取餘數，請輸出 $c n t_{0} \oplus c n t_{1} \oplus \dots \oplus c n t_{k}$ ，其中 $\oplus$ 為 $bitwise xor$ 。

輸入說明

第一行有兩個正整數 $n, m, k$ ，代表要隔離幾天、每天有幾種外賣可以選，和 $Waimai$ 想知道他的總飽足度為 $0 \sim k$ 分別的方法數。

第二行有 $m$ 個數字 $a_{1} \sim a_{m}$ ，代表每個外賣的飽足度。

$1 \leq n \leq 10^{10^{5}}$
$1 \leq m, k \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq k$

輸出說明

請輸出一個整數，代表 $c n t_{0} \oplus c n t_{1} \oplus \dots \oplus c n t_{k}$ 。

範例輸入 #1

2 2 3
2 1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (1%): 3.0s , <1M
不公開測資點#1 (2%): 3.0s , <1M
不公開測資點#2 (2%): 3.0s , <1M
不公開測資點#3 (5%): 3.0s , <1M
不公開測資點#4 (5%): 3.0s , <1M
不公開測資點#5 (15%): 3.0s , <1M
不公開測資點#6 (10%): 3.0s , <10M
不公開測資點#7 (10%): 3.0s , <10M
不公開測資點#8 (12%): 3.0s , <10M
不公開測資點#9 (13%): 3.0s , <10M
不公開測資點#10 (8%): 3.0s , <10M
不公開測資點#11 (8%): 3.0s , <1M
不公開測資點#12 (9%): 3.0s , <10M

提示：

在範例中，有 $9$ 種吃外賣的方法，而在總飽足度 $\leq 3$ 的情況下，總飽足度為 $0$ 的有 $1$ 種，總飽足度為 $1$ 的有 $2$ 種，總飽足度為 $2$ 的有 $3$ 種，總飽足度為 $3$ 的有 $2$ 種，故 $c n t_{0} \oplus c n t_{1} \oplus c n t_{2} \oplus c n t_{3} = 1 \oplus 2 \oplus 3 \oplus 2 = 2$ 。

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

$5 % ： n \leq 50, k \leq 1000$

$10 % ： n \leq 10^{4}, k \leq 1000$

$15 % ： n \leq 10^{10^{5}}, k \leq 1000$

$20 % ： n \leq 50$

$25 % ： n \leq 10^{4}$

$25 % ：無特別限制$

標籤:

NTT 數學

出處:

Caido [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
31051	fire5386 (becaidorz)	h999	簡易題解	667	2022-07-08 16:30