問題一覧 >
教育的問題
No.2272 多項式乗算 mod 258280327
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 29
作問者 : 👑
p-adic
/ テスター :
hotman78
問題文最終更新日: 2023-03-08 12:39:18
問題文
入力に非負整数係数多項式 F(x) と G(x) が与えられます。
非負整数多項式 F(x)G(x) の 各係数を 258280327 で割った余りを計算してください。
入力
入力は以下の形式で標準入力から 4 行で与えられます:
- 1 行目に F の次数 N が与えられます。
- 2 行目に N 以下の各非負整数 i に対する F の i 次係数 Fi が、i の小さい順に半角空白区切りで与えられます。
- 3 行目に G の次数 M が与えられます。
- 4 行目に M 以下の各非負整数 j に対する G の j 次係数 Gj が、j の小さい順に半角空白区切りで与えられます。
ただし零多項式の次数をここでは 0 と定義します。
制約
入力は以下の制約を満たします:
- N は 0≤N≤2×105 を満たす整数
- N 以下の任意の非負整数 i に対し、
- i=N=0ならば Fi は 0<Fi≤1018 を満たす整数
- そうでないならば Fi は 0≤Fi≤1018 を満たす整数
- M は 0≤M≤2×105 を満たす整数
- M 以下の任意の非負整数 j に対し、
- j=M=0 ならば Gj は 0<Gj≤1018 を満たす整数
- そうでないならば Gj は 0≤Gj≤1018 を満たす整数
出力
以下の形式で標準出力に 2 行で出力してください:
- 1 行目に F(x)G(x) の次数 L を出力してください。
- 2 行目に L 以下の各非負整数 k に対する F(x)G(x) の k 次係数を 258280327 で割った余りを k が小さい順に半角空白区切りで出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1
0 1
1
0 1
出力
2
0 0 1
(0+1x)×(0+1x)=0+0x+1x2
の各係数 0,0,1 を 258280327 で割った余りは 0,0,1 です。
サンプル2
入力
1
50000 7
1
1 20000
出力
2
50000 225159026 140000
(50000+7x)×(1+20000x)=50000+1000000007x+140000x2
の各係数 50000,1000000007,140000 を 258280327 で割った余りは 50000,225159026,1400000 です。
サンプル3
入力
1
65536 1
1
1 15232
出力
2
65536 223403372 15232
(65536+1x)×(1+15232x)=65536+998244353x+15232x2
の各係数 65536,998244353,15232 を 258280327 で割った余りは 65536,223403372,15232 です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。