問題一覧 > 通常問題

No.3793 Multishift

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 8
作問者 : hiro1729 / テスター : 👑 AngrySadEight DeltaStruct / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 14190 / 自分の提出
問題文最終更新日: 2026-11-06 06:55:46
yukicoder contest 521 yukimy32 (hiro1729) お誕生日コンテスト (順位表) の他の問題:

問題文

正整数 $N, M$ と長さ $N+1, M+1$ の整数列 $A, B$ が与えられます。多項式 $f(x),g(x)$ を以下のように定義します。

$$\begin{aligned} f(x) &= \sum _{i=0} ^N A_i x^i \\ g(x) &= \sum _{i=0} ^M B_i f(x-i) \end{aligned}$$

$g(x)$ の $x^0, x^1, \ldots, x^N$ の係数をそれぞれ $998244353$ で割った余りを求めてください。

制約

  • $1 \le N, M \le 10^5$
  • $0 \le A_i < 998244353 (0 \le i \le N)$
  • $0 \le B_i < 998244353 (0 \le i \le M)$

入力

$N$ $M$
$A_0$ $A_1$ $\ldots$ $A_N$
$B_0$ $B_1$ $\ldots$ $B_M$

出力

$g(x)$ の $x^i$ の係数を $998244353$ で割った余りを $C_i$ とします。$C$ を以下の形式で出力し、最後に改行してください。

$C_0$ $C_1$ $\ldots$ $C_N$

サンプル

サンプル1
入力
2 2
2 0 1
1 2 3
出力
26 998244337 6

$f(x)=2+x^2$ であり、$g$ は以下のように計算できます。

$$\begin{aligned} g(x)&=1 \times f(x) + 2 \times f(x-1) + 3 \times f(x-2) \\ &= (2+x^2) + 2(2+(x-1)^2) + 3(2+(x-2)^2) \\ &= 26-16x+6x^2 \end{aligned}$$

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。