C - Compose Your Library Editorial

Time Limit: 6 sec / Memory Limit: 2048 MB

配点 : 100100 点

2024 年最大のニュースと言えば，もちろん Yasunori Kinoshita, Baitian Li, "Power Series Composition in Near-Linear Time" (FOCS 2024) の発表ですね．みなさんこぞって実装したり出題したりしたかと存じます．この問題では，多変数への一般化の研究を試みるとともに，想定より高速な解法を募集しているかもしれません．

問題文

正整数 MM と，整数係数多項式 F(t)=∑i=0M−1FitiF(t) = \sum_{i=0}^{M-1} F_i t^i が与えられる．

また，KK 個の正整数 N0,N1,…,NK−1N_0, N_1, \ldots, N_{K-1} と，KK 元整数係数多項式 G(x0,x1,…,xK−1)=∑j0=0N0−1∑j1=0N1−1⋯∑jK−1=0NK−1−1Gjx0j0x1j1⋯xK−1jK−1G(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=j0+N0j1+(N0N1)j2+⋯+(N0N1⋯NK−2)jK−1j = 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≤jk<Nk0 \le j_k < N_k を満たす各整数組 (j0,j1,…,jK−1)(j_0, j_1, \ldots, j_{K-1}) について，合成 F(G(x0,x1,…,xK−1))F(G(x_0, x_1, \ldots, x_{K-1})) の x0j0x1j1⋯xK−1jK−1x_0^{j_0} x_1^{j_1} \cdots x_{K-1}^{j_{K-1}} の係数を 998244353998244353 で割った余りを求めよ．

制約

  • 1≤M≤2161 \le M \le 2^{16}．
  • 0≤Fi<9982443530 \le F_i < 998244353   (0≤i<M0 \le i < M)．
  • 1≤K≤161 \le K \le 16．
  • 2≤N0≤N1≤⋯≤NK−12 \le N_0 \le N_1 \le \cdots \le N_{K-1}．
  • N0N1⋯NK−1≤216N_0 N_1 \cdots N_{K-1} \le 2^{16}．
  • 0≤Gj<9982443530 \le G_j < 998244353   (0≤j<N0N1⋯NK−10 \le j < N_0 N_1 \cdots N_{K-1})．

入力

入力は以下の形式で標準入力から与えられる．

MM
F0F_0 F1F_1 ⋯\cdots FM−1F_{M-1}
KK
N0N_0 N1N_1 ⋯\cdots NK−1N_{K-1}
G0G_0 G1G_1 ⋯\cdots G(N0N1⋯NK−1)−1G_{(N_0 N_1 \cdots N_{K-1}) - 1}

出力

0≤jk<Nk0 \le j_k < N_k を満たす各整数組 (j0,j1,…,jK−1)(j_0, j_1, \ldots, j_{K-1}) について， 合成 F(G(x0,x1,…,xK−1))F(G(x_0, x_1, \ldots, x_{K-1})) の x0j0x1j1⋯xK−1jK−1x_0^{j_0} x_1^{j_1} \cdots x_{K-1}^{j_{K-1}} の係数を 998244353998244353 で割った余りを， j=j0+N0j1+(N0N1)j2+⋯+(N0N1⋯NK−2)jK−1j = j_0 + N_0 j_1 + (N_0 N_1) j_2 + \cdots + (N_0 N_1 \cdots N_{K-2}) j_{K-1} とおいて hjh_j とする．以下の形式で出力せよ．

h0h_0 h1h_1 ⋯\cdots h(N0N1⋯NK−1)−1h_{(N_0 N_1 \cdots N_{K-1}) - 1}

入力例 1Copy

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

出力例 1Copy

Copy
9006004 12004000 36012000 48008000 66010000 74002000

F(t)=4+2000t+1000000t2, G(x0,x1)=3+2x0+6x1+4x0x1+5x12+1x0x12F(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 である．

入力例 2Copy

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

出力例 2Copy

Copy
20 24 36 96 204 456 960 1992 4020 7968

入力例 3Copy

Copy
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

出力例 3Copy

Copy
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

2025-04-03 (Thu)
08:31:42 +00:00