#P5577. [CmdOI2019] 算力训练

[CmdOI2019] 算力训练

题目背景

最近,出题人快乐地学习了如何解一元二次方程。

晚上在宿舍里,出题人梦见了一个使用 kk 进制的国度,入乡随俗嘛,出题人在这里也使用 kk 进制。

当然,这个国度里面的人也懂数学,所以解不出一元二次方程的出题人并没有逃掉算力训练。

题目描述

出题人在纸条上写了 nnkk 进制自然数,由于他很懒,这些数的位数不会太多,都不会超过 mm 位。

为了训练算力,他每次会随意取出一个子序列 (允许一个数都不选) ,然后把这些数都加起来。

他又觉得进位太麻烦了,干脆规定加法不进位

算了几次之后,他突然很想知道自己得到每个数的方案数是多少,可是他太菜了,又不会算。冥思苦想一番之后,突然被起床铃拉出了梦境。

他觉得这个问题很有趣,只好求助于单手虐暴无数代数题的你,来帮忙计算一下。

形式化题意 : 对于一个序列 AA ,定义其权值 W(A)W(A)AA 中元素做 kk 进制不进位加法的和。

给出 m,km,k 和一个长为 nn 的序列 SS。保证 S[0,km)ZS\subseteq [0,k^m)∩Z

对于 t=0,1,2,...,km1t=0,1,2,...,k^m-1 ,分别求出下列式子的值 :

$${\rm Ans}[t]=\sum\limits_{\text{R 是 S 的子序列}}\big[W(R)=t\big] $$

注 :根据正确的题意可推知 t=0km1Ans[t]=2n\sum\limits_{t=0}^{k^m-1}{\rm Ans}[t]=2^n

输入格式

第一行三个整数 n,k,mn,k,m ,意义为题目中所述。

第二行 nn 个整数,之间用空格隔开,表示纸条上的数字。

(注意,纸条上的数均为 kk 进制数)

输出格式

kmk^m 行,你需要在第 ii 行输出得到数 i1i-1 的方案数,答案对 998244353998244353 取模。

3 5 1
1 2 3
2
2
1
2
1
5 6 1
1 1 4 5 1 4
8
7
4
2
4
7

提示

样例解释

对于样例#1,共有 23=82^3=8 种选取子序列的方法:

  1. 什么都不选,和为 00
  2. 11 ,和为 11
  3. 22 ,和为 22
  4. 33 ,和为 33
  5. 1+21+2 ,和为 33
  6. 1+31+3 ,和为 44
  7. 2+32+3 ,和为 00 (由于是 55 进制,本来要变成 1010 的,但是不进位就只剩下 00 了)
  8. 1+2+31+2+3,和为 11

综上,得到 0,1,2,3,4 的方案数分别是 2,2,1,2,1

数据范围和约定

测试点编号 n k m 总分数
#1 2020 55 44 55
#2 10001000
#3~4 10610^6 55 1010
#5 66
#6~7 77 2020
#8 2020 66 44 55
#9 10001000
#10~11 10610^6 1010
#12~14 66 3030