← 返回题目列表

AtCoder · xmascon24_c

C. 组成你的图书馆

中文机器翻译题面 查看原题

配点 : 100 点

说到 2024 年最大的新闻,当然 Yasunori Kinoshita, Baitian Li, 《近线性时间的幂级数合成》(FOCS 2024) 的发表吧。我想大家都争相实现或出题了。在这个问题中,也许会尝试研究向多变量的一般化,同时征求比预期更快速的解法。

問題文

正整数 M 以及,给定整数系数多项式 F(t) = \sum_{i=0}^{M-1} F_i t^i 。

另外, 如果我们只为第K 正整数 找出满足以下条件的 N_0, N_1, \ldots, N_{K-1} 和K 元整数係数多項式 G(x_0, x_1, \ldots, x_{K-1}) = \displaystyle\sum_{j_0=0}^{N_0-1} \displaystyle\sum_{j_1=0}^{N_1-1} \cdots \displaystyle\sum_{j_{K-1}=0}^{N_{K-1}-1} G_j x_0^{j_0} x_1^{j_1} \cdots x_{K-1}^{j_{K-1}} 。这里,在和式的内部,对于 j = j_0 + N_0 j_1 + (N_0 N_1) j_2 + \cdots + (N_0 N_1 \cdots N_{K-2}) j_{K-1} 。

0 \le j_k < N_k 满足条件的每一个整数组合 (j_0, j_1, \ldots, j_{K-1}) ,进行合成 F(G(x_0, x_1, \ldots, x_{K-1})) 可以得到第 x_0^{j_0} x_1^{j_1} \cdots x_{K-1}^{j_{K-1}} 的系数 998244353 求余数。 打印除以

制約

  • 1 \le M \le 2^{16}.
  • 0 \le F_i < 998244353   (0 \le i < M).
  • 1 \le K \le 16.
  • 2 \le N_0 \le N_1 \le \cdots \le N_{K-1}.
  • N_0 N_1 \cdots N_{K-1} \le 2^{16}.
  • 0 \le G_j < 998244353   (0 \le j < N_0 N_1 \cdots N_{K-1}).

入力

输入是按以下格式从标准输入给出的。

M
F_0 F_1 \cdots F_{M-1}
K
N_0 N_1 \cdots N_{K-1}
G_0 G_1 \cdots G_{(N_0 N_1 \cdots N_{K-1}) - 1}

出力

0 \le j_k < N_k 满足条件的每一个整数组合 (j_0, j_1, \ldots, j_{K-1}) ,关于 F(G(x_0, x_1, \ldots, x_{K-1})) 可以得到第 x_0^{j_0} x_1^{j_1} \cdots x_{K-1}^{j_{K-1}} 的系数 998244353 取余后的结果, j = j_0 + N_0 j_1 + (N_0 N_1) j_2 + \cdots + (N_0 N_1 \cdots N_{K-2}) j_{K-1} 定义为 h_j 。请按以下格式输出。

h_0 h_1 \cdots h_{(N_0 N_1 \cdots N_{K-1}) - 1}

入力例 1

3
4 2000 1000000
2
2 3
3 2 6 4 5 1

出力例 1

9006004 12004000 36012000 48008000 66010000 74002000

F(t) = 4 + 2000 t + 1000000 t^2,\, G(x_0, x_1) = 3 + 2 x_0 + 6 x_1 + 4 x_0 x_1 + 5 x_1^2 + 1 x_0 x_1^2 。


入力例 2

4
20 24 12 24
1
10
0 1 1 2 3 5 8 13 21 34

出力例 2

20 24 36 96 204 456 960 1992 4020 7968

入力例 3

15
2 3 6 11 23 47 106 235 551 1301 3159 7741 19320 48629 123867
3
3 3 3
1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436

出力例 3

205001 2733669 22444763 8201007 115532895 978118598 182867184 683781124 283511483 82010070 135215245 487076637 271695954 473451928 217234716 349364028 711882268 472200539 360235417 248161311 666997398 886133207 465643853 863287257 136771343 714472215 407369010