No.2272 多項式乗算 mod 258280327
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : 👑
p-adic
/ テスター :
hotman78
タグ : / 解いたユーザー数 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$ 次係数 $F_i$ が、$i$ の小さい順に半角空白区切りで与えられます。
- $3$ 行目に $G$ の次数 $M$ が与えられます。
- $4$ 行目に $M$ 以下の各非負整数 $j$ に対する $G$ の $j$ 次係数 $G_j$ が、$j$ の小さい順に半角空白区切りで与えられます。
ただし零多項式の次数をここでは $0$ と定義します。
制約
入力は以下の制約を満たします：
- $N$ は $0 \leq N \leq 2 \times 10^5$ を満たす整数
- $N$ 以下の任意の非負整数 $i$ に対し、
- $i = N \neq 0$ならば $F_i$ は $0 < F_i \leq 10^{18}$ を満たす整数
- そうでないならば $F_i$ は $0 \leq F_i \leq 10^{18}$ を満たす整数
- $M$ は $0 \leq M \leq 2 \times 10^5$ を満たす整数
- $M$ 以下の任意の非負整数 $j$ に対し、
- $j = M \neq 0$ ならば $G_j$ は $0 < G_j \leq 10^{18}$ を満たす整数
- そうでないならば $G_j$ は $0 \leq G_j \leq 10^{18}$ を満たす整数
出力
以下の形式で標準出力に $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
$\displaystyle (0 + 1x) \times (0 + 1x) = 0 + 0x + 1x^2 $
の各係数 $0,0,1$ を $258280327$ で割った余りは $0,0,1$ です。
サンプル2
入力
1 50000 7 1 1 20000
出力
2 50000 225159026 140000
$\displaystyle (50000 + 7x) \times (1 + 20000x) = 50000 + 1000000007x + 140000x^2 $
の各係数 $50000,1000000007,140000$ を $258280327$ で割った余りは $50000,225159026,1400000$ です。
サンプル3
入力
1 65536 1 1 1 15232
出力
2 65536 223403372 15232
$\displaystyle (65536 + 1x) \times (1 + 15232x) = 65536 + 998244353x + 15232x^2 $
の各係数 $65536,998244353,15232$ を $258280327$ で割った余りは $65536,223403372,15232$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。