59 . 紀念幣

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

45.1% (41/91)

Tags

ioicamp ioicamp-2024

Description

為了迎接 $11 \times (45 + 1) \times 4$ 年的到來，我們決定發行一些新的紀念幣。設計好的款式一共有 $N$ 種，每一種款式都有一個面額，其中幾種款式將被選中並發行。

為了兼顧紀念價值與便利性，當你要購買任何價格為正整數的東西時，都要能只使用若干個發行的紀念幣來進行付款與找零，並支付出剛好的金額。例如只發行一百元與一千元就是個糟糕的選擇，因為你無法支付任何低於一百元的金額。

現在你要幫忙計算發行的紀念幣有幾種不同的選擇，兩種選擇不同的意思是有至少一種紀念幣只在其中一個選擇中被選上。為了控制紀念幣的種類數，請你對每一個發行的種類數分別算出該數量的方法數，對 $998244353$ 取模。

Input Format

輸入共有兩行。第一行包含一個正整數 $N$，代表有幾種紀念幣。第二行包含 $N$ 個正整數 $a_1, a_2, \ldots, a_N$，代表每種紀念幣的面額。

  • $1 \le N \le 10^ 6$
  • $1 \le a_i \le 2 \times 10^ 6$

Output Format

輸出一行，包含 $N$ 個以空格隔開的整數，第 $i$ 個代表發行 $i$ 種紀念幣的方法數除以 $998244353$ 的餘數。

Sample Input 1

7
11 45 1 4 19 19 810

Sample Output 1

1 18 35 35 21 7 1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~45 無額外限制 100

Testdata and Limits

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