Codeforces Round 789 (Div. 1) |
---|
Закончено |
У Tokitsukaze есть последовательность длины $$$n$$$. Она очень любит драгоценные камни. Есть $$$n$$$ видов драгоценных камней. Камни $$$i$$$-го вида находятся на $$$i$$$-й позиции, и на этой позиции есть $$$a_i$$$ камней этого типа. Определим $$$G(l,r)$$$ как мультимножество, содержащее все драгоценные камни на отрезке $$$[l,r]$$$.
Мультимножество драгоценных камней может быть представлено в виде $$$S=[s_1,s_2,\ldots,s_n]$$$, которое представляет собой неотрицательную целочисленную последовательность длины $$$n$$$ и означает, что $$$S$$$ содержит $$$s_i$$$ драгоценных камней $$$i$$$-го вида в мультимножестве. Мультимножество $$$T=[t_1,t_2,\ldots,t_n]$$$ является мультиподмножеством $$$S=[s_1,s_2,\ldots,s_n]$$$ тогда и только тогда, когда $$$t_i\le s_i$$$ для любого $$$i$$$, удовлетворяющего $$$1\le i\le n$$$.
Теперь, учитывая два положительных целых числа $$$k$$$ и $$$p$$$, вам нужно вычислить результат
$$$$$$\sum_{l=1}^n \sum_{r=l}^n\sum\limits_{[t_1,t_2,\cdots,t_n] \subseteq G(l,r)}\left(\left(\sum_{i=1}^n p^{t_i}t_i^k\right)\left(\sum_{i=1}^n[t_i>0]\right)\right),$$$$$$
где $$$[t_i>0]=1$$$, если $$$t_i>0$$$ и $$$[t_i>0]=0$$$, если $$$t_i=0$$$.
Так как ответ может быть довольно большим, выведите его по модулю $$$998\,244\,353$$$.
Первая строка содержит три целых числа $$$n$$$, $$$k$$$ и $$$p$$$ ($$$1\le n \le 10^5$$$; $$$1\le k\le 10^5$$$; $$$2\le p\le 998\,244\,351$$$) — длина последовательности, числа $$$k$$$ и $$$p$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 998\,244\,351$$$) — количество камней на $$$i$$$-й позиции .
Выведите одно целое число — результат по модулю $$$998\,244\,353$$$.
5 2 2 1 1 1 2 2
6428
6 2 2 2 2 2 2 2 3
338940
Название |
---|