题解

思路

一次前缀和会把序列的生成函数乘上 $1/(1-z)$。连续做 $k+1$ 次前缀和后，$a_j$ 对第 $t$ 项的系数是 $\binom{t-j+k}{k}$。把下标向后平移 $k-1$，就得到题目中的 $\binom{i-j+1}{k}$。

做法

小规模

先生成数组，再对每个 $i$ 直接枚举 $j$ 并计算组合数，复杂度 $O(n^2k)$。

$k=1$

此时 $b_i=\sum_{j=1}^i(i-j+1)a_j$，维护普通前缀和与二次前缀和即可在线求出。

满分算法

维护 $k+1$ 层前缀和 $s_1,\ldots,s_{k+1}$。读到 $a_t$ 时，依次令 $s_1\leftarrow s_1+a_t$，并对 $2\le r\le k+1$ 令 $s_r\leftarrow s_r+s_{r-1}$。

所有加法对 $998244353$ 取模。此时 $s_{k+1}$ 正是 $b_{t+k-1}$。若该下标不超过 $n$，将它乘以下标后异或进答案。

正确性说明

做 $k+1$ 次前缀和后，$a_j$ 在位置 $t$ 的系数为 $\binom{t-j+k}{k}$。令 $i=t+k-1$，该系数变成 $\binom{i-j+1}{k}$，与 $b_i$ 的定义完全一致。由于 $j>i-k+1$ 时组合数为零，未被在线过程读取的后缀项也不会影响对应答案。逐个异或全部合法下标即得到所求值。

复杂度

满分算法时间复杂度 $O(nk)$，额外空间复杂度 $O(k)$；小规模算法为 $O(n^2k)$。