問題一覧 > 教育的問題

No.2272 多項式乗算 mod 258280327

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : 👑 p-adicp-adic / テスター : hotman78hotman78
0 ProblemId : 8595 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-08 12:39:18

問題文

入力に非負整数係数多項式 F(x)F(x)G(x)G(x) が与えられます。

非負整数多項式 F(x)G(x)F(x) G(x) の 各係数を 258280327258280327 で割った余りを計算してください。

入力

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

  • 11 行目に FF の次数 NN が与えられます。
  • 22 行目に NN 以下の各非負整数 ii に対する FFii 次係数 FiF_i が、ii の小さい順に半角空白区切りで与えられます。
  • 33 行目に GG の次数 MM が与えられます。
  • 44 行目に MM 以下の各非負整数 jj に対する GGjj 次係数 GjG_j が、jj の小さい順に半角空白区切りで与えられます。

ただし零多項式の次数をここでは 00 と定義します。

制約

入力は以下の制約を満たします:

  • NN0N2×1050 \leq N \leq 2 \times 10^5 を満たす整数
  • NN 以下の任意の非負整数 ii に対し、
    • i=N0i = N \neq 0ならば FiF_i0<Fi10180 < F_i \leq 10^{18} を満たす整数
    • そうでないならば FiF_i0Fi10180 \leq F_i \leq 10^{18} を満たす整数
  • MM0M2×1050 \leq M \leq 2 \times 10^5 を満たす整数
  • MM 以下の任意の非負整数 jj に対し、
    • j=M0j = M \neq 0 ならば GjG_j0<Gj10180 < G_j \leq 10^{18} を満たす整数
    • そうでないならば GjG_j0Gj10180 \leq G_j \leq 10^{18} を満たす整数

出力

以下の形式で標準出力に 22 行で出力してください:

  • 11 行目に F(x)G(x)F(x) G(x) の次数 LL を出力してください。
  • 22 行目に LL 以下の各非負整数 kk に対する F(x)G(x)F(x) G(x)kk 次係数を 258280327258280327 で割った余りを kk が小さい順に半角空白区切りで出力してください。

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

サンプル

サンプル1
入力
1
0 1
1
0 1
出力
2
0 0 1

(0+1x)×(0+1x)=0+0x+1x2\displaystyle (0 + 1x) \times (0 + 1x) = 0 + 0x + 1x^2

の各係数 0,0,10,0,1258280327258280327 で割った余りは 0,0,10,0,1 です。

サンプル2
入力
1
50000 7
1
1 20000
出力
2
50000 225159026 140000

(50000+7x)×(1+20000x)=50000+1000000007x+140000x2\displaystyle (50000 + 7x) \times (1 + 20000x) = 50000 + 1000000007x + 140000x^2

の各係数 50000,1000000007,14000050000,1000000007,140000258280327258280327 で割った余りは 50000,225159026,140000050000,225159026,1400000 です。

サンプル3
入力
1
65536 1
1
1 15232
出力
2
65536 223403372 15232

(65536+1x)×(1+15232x)=65536+998244353x+15232x2\displaystyle (65536 + 1x) \times (1 + 15232x) = 65536 + 998244353x + 15232x^2

の各係数 65536,998244353,1523265536,998244353,15232258280327258280327 で割った余りは 65536,223403372,1523265536,223403372,15232 です。

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