/ 
Time Limit: 6 sec / Memory Limit: 2048 MB
配点 : 100 点
2024 年最大のニュースと言えば，もちろん Yasunori Kinoshita, Baitian Li, "Power Series Composition in Near-Linear Time" (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