TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4083
  • 問題
  • P4083【模板】拉格朗日插值
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,128MB
    問題説明

    这是一道模板题。

    由小学知识可知 \(n\) 个点 \((x_i,y_i)\) 可以唯一地确定一个多项式 \(y=f(x)\)

    现在,给定这 \(n\) 个点,请你确定这个多项式,并求出 \(f(k) \; mod \; 998244353\) 的值。

    入力形式

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

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

    出力形式

    一行一个整数,表示 \(f(k) \; mod \; 998244353\) 的值。

    サンプル入力 1

    3 100
    1 4
    2 9
    3 16

    サンプル出力 1

    10201

    サンプル入力 2

    3 100
    1 1
    2 2
    3 3

    サンプル出力 2

    100

    ヒント

    样例一中的多项式为 \(f(x)=x^2+2x+1\)\(f(100)=10201\)

    样例二中的多项式为 \(f(x)=x\)\(f(100)=100\)


    $1 \le n \le 2 \times 10^3$,$1 \le x_i,y_i,k < 998244353$,\(x_i\) 两两不同。