P15113 [Aboi 2077] Hero

[](https://www.bilibili.com/video/BV1osSEYGEMd)

将 $[1,n]$ 中的整数划分为 $m$ 个集合 $S_1,S_2,\cdots,S_m$，集合间按照其中的最小值 $\min\{S_i\}$ 从小到大排序，记数 $i$ 在第 $p_i$ 个集合中。 唐吉诃德定义整数数对 $(i,j)$ 是**逆序对**，如果： - $i\in[1,n],j\in[1,m]$； - $p_i\min\{S_j\}$。 称一个划分方案 $P=\{S_1,S_2,\cdots,S_m\}$ 的**价值**为 $q^{\text{inv}(P)}$，其中 $\text{inv}(P)$ 为该划分方案中的逆序对个数。 唐吉诃德给了你两个任务： 1. $n$ 固定时，对于 $[1,n]$ 中的每个整数 $m$，求所有划分方案的价值之和； 2. $m$ 固定时，对于 $[m,m+k-1]$ 中的每个整数 $n$，求所有划分方案的价值之和。 两问答案均对 $998244353$ 取模。

一行四个正整数 $n,m,k,q$。

第一行输出 $n$ 个整数，第 $i$ 个整数表示 $n$ 固定、$m=i$ 时的答案； 第二行输出 $k$ 个整数，第 $i$ 个整数表示 $m$ 固定、$n=m+i-1$ 时的答案。 两问答案均对 $998244353$ 取模。

对于所有数据，$1\le n,m,k\le10^6$，$0\le q