53 . IOIC 禮品店

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

10.0% (1/10)

Tags

ioicamp ioicamp-2024

Description

在 IOIC 禮品店的庫存裡，放著 N 種禮物。這些禮物被分成 K 類，第 i 種禮物為第 ai 類，且價值為 bi（為正整數）。保證同類別同價值的禮物至多只有 998244352 個，且每一類別都至少有一種禮物。

參加 IOIC 的優秀學生 Wiwi 在前幾天的比賽獲得了 M 張禮物兌換券，第 j 張可以任選一個第 cj 類的禮物。興奮的 Wiwi 帶著他贏得的兌換券，打算找禮品店的店長 Hoho 兌換禮物。經過計算後，店長告訴她，她最多可以換到總價值不超過 X 的禮物，而且還告訴她在不一定要使用所有兌換券的前提下，他有 ni 種方法可以換到價值總和為 i 的禮物們。這麼多的選擇讓 Wiwi 暈頭轉向，於是她決定將這些數字抄回家再慢慢決定。

回家後，她想著想著決定同一類的禮物只想至多使用一張兌換券。而在思考要選擇哪些禮物的同時，她不小心趴在書桌上睡著了。隔天早上醒來，Wiwi 發現她竟然忘記了她有幾張兌換券，也不記得禮物有哪些，只剩眼前抄回來的數字們。
請你幫幫慌亂的 Wiwi，從紙上的資訊回推出她有哪些兌換券，並告訴她在同一類的禮物只想至多使用一張兌換券的前提下，想要換到價值總和為 i 的禮物們有幾種方法？

若有多組解，請輸出 M 最大的前提下，K 最小的那組。

Input Format

輸入共有兩行。第一行包含一個正整數 X。第二行包含 X 個以空白分隔的非負整數 ni′，表示 ni 除以 998244353 的餘數。

  • X≤5×104
  • ni′<998244353

Output Format

請輸出一行，包含 X 個以空白分隔的非負整數，第 i 個表示按照 Wiwi 的要求下，買到總價值為 i 的方法數除以 998244353 的餘數。

Sample Input 1

5
2 2 2 1 0

Sample Output 1

1 1 1 0 0

Sample Input 2

6
13 69 191 290 228 72

Sample Output 2

6 11 6 0 0 0

Hints

範測一中，(a,b)i=(1,1),(2,1),(2,2),(2,3) 且 cj=1,2 是一組可行的解。
可以證明 M 最大的解為 (a,b)i=(1,1),(2,2) 且 cj=1,1,2。

範測二中，M 最大的解為 (a,b)i=(1,1),(2,1),(2,1),(3,1),(3,1),(3,1) 且 cj=1,2,2,2,3,3。
此範測因此滿足子任務三的條件。

Problem Source

IOICamp 2024 Day6 pF

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~11, 44~46 X=2 10
3 1, 12~20 存在解滿足 bi=1，且一類玩具至多只有 100 種 20
4 0~11, 21~32, 44~46 X≤103 30
5 0~46 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 4 5
1 3000 262144 65536 1 3 4 5
2 3000 262144 65536 2 4 5
3 3000 262144 65536 2 4 5
4 3000 262144 65536 2 4 5
5 3000 262144 65536 2 4 5
6 3000 262144 65536 2 4 5
7 3000 262144 65536 2 4 5
8 3000 262144 65536 2 4 5
9 3000 262144 65536 2 4 5
10 3000 262144 65536 2 4 5
11 3000 262144 65536 2 4 5
12 3000 262144 65536 3 5
13 3000 262144 65536 3 5
14 3000 262144 65536 3 5
15 3000 262144 65536 3 5
16 3000 262144 65536 3 5
17 3000 262144 65536 3 5
18 3000 262144 65536 3 5
19 3000 262144 65536 3 5
20 3000 262144 65536 3 5
21 3000 262144 65536 4 5
22 3000 262144 65536 4 5
23 3000 262144 65536 4 5
24 3000 262144 65536 4 5
25 3000 262144 65536 4 5
26 3000 262144 65536 4 5
27 3000 262144 65536 4 5
28 3000 262144 65536 4 5
29 3000 262144 65536 4 5
30 3000 262144 65536 4 5
31 3000 262144 65536 4 5
32 3000 262144 65536 4 5
33 3000 262144 65536 5
34 3000 262144 65536 5
35 3000 262144 65536 5
36 3000 262144 65536 5
37 3000 262144 65536 5
38 3000 262144 65536 5
39 3000 262144 65536 5
40 3000 262144 65536 5
41 3000 262144 65536 5
42 3000 262144 65536 5
43 3000 262144 65536 5
44 3000 262144 65536 2 4 5
45 3000 262144 65536 2 4 5
46 3000 262144 65536 2 4 5
Submit
Back to Top