CF1677F Tokitsukaze and Gems

时津风有一个长度为 $n$ 的序列。她非常喜欢宝石。一共有 $n$ 种宝石，第 $i$ 种宝石位于第 $i$ 个位置，在该位置上有 $a_i$ 颗同种宝石。定义 $G(l,r)$ 为区间 $[l,r]$（包含两端）上所有宝石组成的多重集。 一个宝石多重集可以表示为 $S=[s_1,s_2,\ldots,s_n]$，这是一个长度为 $n$ 的非负整数序列，表示 $S$ 中包含 $s_i$ 颗第 $i$ 种宝石。若对于任意 $1\le i\le n$，都有 $t_i\le s_i$，则多重集 $T=[t_1,t_2,\ldots,t_n]$ 是 $S=[s_1,s_2,\ldots,s_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$ 取模后的值。

由 ChatGPT 4.1 翻译