h999: 線上外賣學習
Tags : NTT 數學
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-06 23:49

Content

$\text{Waimai}$ 的班上有人確診了,於是 $\text{Waimai}$ 要居家隔離。

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

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

Input

第一行有兩個正整數 $n, m, k$,代表要隔離幾天、每天有幾種外賣可以選,和 $\text{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$
Output

請輸出一個整數,代表 $cnt_0 \oplus cnt_1 \oplus \dots \oplus cnt_k$。

Sample Input #1
2 2 3
2 1
Sample Output #1
2
測資資訊:
記憶體限制: 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
Hint :

在範例中,有 $9$ 種吃外賣的方法,而在總飽足度 $\leq 3$ 的情況下,總飽足度為 $0$ 的有 $1$ 種,總飽足度為 $1$ 的有 $2$ 種,總飽足度為 $2$ 的有 $3$ 種,總飽足度為 $3$ 的有 $2$ 種,故 $cnt_0 \oplus cnt_1 \oplus cnt_2 \oplus cnt_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\%:無特別限制$

Tags:
NTT 數學
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
31051 fire5386(Penguin07) h999
簡易題解
127 2022-07-08 16:30