Floor Div Convolution?

2 secs 1024 MB
ecottea's icon ecottea

問題文

長さ NN の整数列 A1,A2,,ANA_1, A_2, \ldots, A_N と長さ MM の整数列 B1,B2,,BMB_1, B_2, \ldots, B_M が与えられます.以下の式で定まる長さ N+1N+1 の整数列 C0,C1,,CNC_0, C_1, \ldots, C_Nmod  998244353\bmod \; 998244353 で求めてください.

Ck=i/j=kAiBj(k=0,1,,N)C_k = \sum_{\lfloor i / j \rfloor = k} A_i B_j \quad (k = 0, 1, \ldots, N)

ただし \lfloor \cdot \rfloor は床関数であり,和は 1iN1 \leq i \leq N1jM1 \leq j \leq M の範囲に渡ってとるものとします.

制約

  • 1N,M2×1051 \leq N, M \leq 2 \times 10^5
  • 0Ai<998244353(i=1,2,,N)0 \leq A_i \lt 998244353 \quad (i = 1, 2, \ldots, N)
  • 0Bj<998244353(j=1,2,,M)0 \leq B_j \lt 998244353 \quad (j = 1, 2, \ldots, M)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます.

NN MM
A1A_1 A2A_2 \ldots ANA_N
B1B_1 B2B_2 \ldots BMB_M

出力

長さ N+1N+1 の整数列 C0,C1,,CNC_0, C_1, \ldots, C_N の各項を 998244353998244353 で割った余りを半角空白区切りで一行に出力してください.

最後に改行してください.

サンプル

入力1
3 2
2 3 5
3 2
出力1
4 22 9 15

例えば ij=1\lfloor \frac{i}{j} \rfloor = 1 となる iijj の組み合わせは (i,j)=(1,1),(2,2),(3,2)(i, j) = (1, 1), (2, 2), (3, 2) であり,

C1=A1B1+A2B2+A3B2=2×3+3×2+5×2=22C_1 = A_1 B_1 + A_2 B_2 + A_3 B_2 = 2 \times 3 + 3 \times 2 + 5 \times 2 = 22

となります.

入力2
1 1
998244352
998244352
出力2
0 1

998244353998244353 で割った余りを出力してください.

入力3
5 8
3 1 4 1 5
9 2 6 5 3 5 8 9
出力3
405 142 21 36 9 45

Submit


Go (1.21)