P8807 - [ARC120F2] Wine Thief

题目

P8807[ARC120F2] Wine Thief

限制 : 时间限制 : - MS 空间限制 : 524288 KB

评测说明 : 10s,512MB

问题描述

\(N\) 瓶酒排成一行， \(i\) 瓶价值 \(A_i\) 。小偷要偷恰好 \(K\) 瓶，任意连续 \(D\) 瓶至多偷 \(1\) 瓶，求所有偷取方案的价值总和的总和 \(\bmod 998\;244\;353\) 。

输入格式

第一行 \(N,K,D\) 。

第二行 \(A_1,\cdots,A_N\) 。

输出格式

一个整数答案。

样例输入 1

4 2 2
1 4 2 3

样例输出 1

样例输入 2

5 2 3
1 5 7 7 3

样例输出 2

样例输入 3

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

样例输出 3

228955567

提示

样例1解释

偷第 \(1,3\) 瓶，价值总和为 \(3\)
偷第 \(1,4\) 瓶，价值总和为 \(4\)
偷第 \(2,4\) 瓶，价值总和为 \(7\)

样例2解释

偷第 \(1,4\) 瓶，价值总和为 \(8\)
偷第 \(1,5\) 瓶，价值总和为 \(4\)
偷第 \(2,5\) 瓶，价值总和为 \(8\)

数据范围

\(2\leq D\leq N\leq 10^6\)
\(K\leq \lceil \frac ND\rceil\)
\(1\leq A_i\lt 998\;244\;353\)