配点 : 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