F2 - Wine Thief

Contest Duration: 2021-05-23(Sun) 11:00 - 2021-05-23(Sun) 13:00 (local time) (120 minutes) Back to Home

F2 - Wine Thief Editorial

Time Limit: 10 sec / Memory Limit: 1024 MB

配点 : $800$ 点

問題文

問題 F と問題 F2 は同じ問題ですが、制約と実行時間制限が異なります。

高橋君の倉庫には $N$ 本のワインがあり、左右方向 $1$ 列に並んでいます。左から $i$ 番目のワインの美味しさは $A_i$ です。
青木君は今からこの $N$ 本のうち、ちょうど $K$ 本を選んで盗みます。しかし、高橋君は注意深いので、以下の条件が満たされると盗まれたことに気付いてしまいます。

連続で並ぶ $D$ 本のワインであって、そのうち $2$ 本以上盗まれているようなものが存在する

高橋君に気付かれないような全ての盗み方について、盗んだワインの美味しさの和を求め、それを足し合わせた値を求めてください。
なお、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください。

制約

$2 \le D \le N \le 10^6$
$1 \le K \le \left\lceil \frac{N}{D} \right\rceil$ （ $\left\lceil x \right\rceil$ は $x$ 以上の最小の整数を表す）
$1 \le A_i \lt 998244353$
入力に含まれる値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$   $D$ 
 $A_1$   $A_2$   $A_3$   $\dots$   $A_N$

出力

答えを $998244353$ で割った余りを出力せよ。

入力例 1Copy

Copy

4 2 2
1 4 2 3

出力例 1Copy

Copy

盗み方と盗んだワインの美味しさの和は以下の通りです。

左から $1$ 本目のワインと $3$ 本目のワインを盗んだ場合 : 美味しさの和は $1 + 2 = 3$
左から $1$ 本目のワインと $4$ 本目のワインを盗んだ場合 : 美味しさの和は $1 + 3 = 4$
左から $2$ 本目のワインと $4$ 本目のワインを盗んだ場合 : 美味しさの和は $4 + 3 = 7$

よって答えは $3 + 4 + 7 = 14$ となります。

入力例 2Copy

Copy

5 2 3
1 5 7 7 3

出力例 2Copy

Copy

盗み方と盗んだワインの美味しさの和は以下の通りです。

左から $1$ 本目のワインと $4$ 本目のワインを盗んだ場合 : 美味しさの和は $1 + 7 = 8$
左から $1$ 本目のワインと $5$ 本目のワインを盗んだ場合 : 美味しさの和は $1 + 3 = 4$
左から $2$ 本目のワインと $5$ 本目のワインを盗んだ場合 : 美味しさの和は $5 + 3 = 8$

入力例 3Copy

Copy

18 4 4
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094 208762450 787961742 90197530 77329823 193815114 707323467

出力例 3Copy

Copy

228955567

Score : $800$ points

Problem Statement

Problems F and F2 have the same Problem Statement but different Constraints and Time Limits.

There are $N$ bottles of wine in Takahashi's cellar, arranged in a row from left to right.
The tastiness of the $i$ -th bottle from the left is $A_i$ .
Aoki will choose $K$ bottles from these $N$ and steal them. However, Takahashi is careful enough to notice the theft if the following condition is satisfied:

There exist $D$ consecutive bottles such that two or more of them are stolen.

For every way of stealing bottles without getting noticed by Takahashi, find the total tastiness of the bottles stolen, and then find the sum of all those values.
Since the sum can be enormous, print it modulo $998244353$ .

Constraints

$2 \le D \le N \le 10^6$
$1 \le K \le \left\lceil \frac{N}{D} \right\rceil$ ( $\left\lceil x \right\rceil$ represents the smallest integer not less than $x$ .)
$1 \le A_i \lt 998244353$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$   $D$ 
 $A_1$   $A_2$   $A_3$   $\dots$   $A_N$

Output

Print the sum modulo $998244353$ .

Sample Input 1Copy

Copy

4 2 2
1 4 2 3

Sample Output 1Copy

Copy

The possible ways to steal bottles and the total tastiness for each of them are as follows:

Steal the $1$ -st and $3$ -rd bottles from the left, for the total tastiness of $1 + 2 = 3$ .
Steal the $1$ -st and $4$ -th bottles from the left, for the total tastiness of $1 + 3 = 4$ .
Steal the $2$ -nd and $4$ -th bottles from the left, for the total tastiness of $4 + 3 = 7$ .

Thus, the answer is $3 + 4 + 7 = 14$ .

Sample Input 2Copy

Copy

5 2 3
1 5 7 7 3

Sample Output 2Copy

Copy

The possible ways to steal bottles and the total tastiness for each of them are as follows:

Steal the $1$ -st and $4$ -th bottles from the left, for the total tastiness of $1 + 7 = 8$ .
Steal the $1$ -st and $5$ -th bottles from the left, for the total tastiness of $1 + 3 = 4$ .
Steal the $2$ -nd and $5$ -th bottles from the left, for the total tastiness of $5 + 3 = 8$ .

Sample Input 3Copy

Copy

18 4 4
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094 208762450 787961742 90197530 77329823 193815114 707323467

Sample Output 3Copy

Copy

228955567