TouchStone
  Please Login
ログイン 登録
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4421
  • 問題
  • P4421快速拉格朗日插值
    制限 : 時間制限 : - MS   メモリ制限 : 524288 KB
    審判説明 : 5s
    問題説明

    给定 \(n\) 个点 \((x_i,y_i)\) 可以唯一地确定一个多项式 \(y=f(x)\)

    现在,给定这 \(n\) 个点,请你确定这个多项式的系数 \(\bmod 998244353\) 的值。

    入力形式

    第一行两个整数 \(n\)

    接下来 \(n\) 行,第 \(i\) 行两个整数 \(x_i , y_i\)

    出力形式

    一行 \(n-1\) 个整数,依次是 \(x^0 \sim x^{n-1}\) 的系数 \(\bmod 998,244,353\) 的值。

    サンプル入力

    5
    1 1
    2 3
    3 10
    4 4   
    5 3

    サンプル出力

    58 499122063 73 998244335 499122178

    ヒント

    \(1 \le n \le 100\ 000\)\(1 \le x_i,y_i < 998244353\)\(x_i\) 两两不同。

    数据有5组,分别是 \(n=2\ 000,\quad 30\ 000,\quad 60\ 000,\quad 80\ 000,\quad 100\ 000\)

    请适当优化常数!