問題一覧 > 通常問題

No.1938 Lagrange Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : noya2noya2 / テスター : tassei903tassei903 nok0nok0 tatyamtatyam
3 ProblemId : 6856 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-11 00:31:11

問題文

$N$ 個の整数の組 $(x_1,y_1), \dots ,(x_N,y_N)$ が与えられます。

$1\le i\le N$ なる任意の $i$ について、$x$ の $N-2$ 次以下の多項式 $F_i(x)$ を以下を満たすように定めます。

  • $1\le j\le N$ かつ $i\neq j$ を満たす任意の $j$ について $F_i(x_j)=y_j$

  • $\displaystyle F(x)=\sum_{i=1}^{N} F_i(x)$ とするとき、$F(X)$ は有理数であることが示せるので $\bmod 998244353$ で求めてください。

    有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。 ここで、$x,y$ は整数であり、$x$ は $998244353$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。 そして、$xz\equiv y\ (\bmod 998244353)$ を満たすような $0$ 以上 $998244352$ 以下の唯一の整数 $z$ を出力してください。

    ただし、この問題の制約下で答えは一意に定まることが証明できます。

    制約

  • 入力はすべて整数
  • $2\le N\le 10^4$
  • $0\le X\lt 998244353$
  • $0\le x_i,y_i\lt 998244353$
  • $x_i\neq x_j\ (i\neq j)$
  • 入力

    $N\ X$
    $x_1\ y_1$
    $x_2\ y_2$
    $\quad\vdots$
    $x_N\ y_N$
    

    出力

    $F(X)\ (\bmod 998244353)$ を $1$ 行に出力してください。

    サンプル

    サンプル1
    入力
    3 3
    0 0
    1 1
    2 4
    出力
    16

    $F_1(x)=3x-2,\ F_2(x)=2x,\ F_3(x)=x$ です。

    $F(x)=6x-2$ なので、$F(3)=16$ を出力します。

    サンプル2
    入力
    6 15
    9 6
    15 14
    10 15
    1 0
    2 8
    3 17
    出力
    650

    サンプル3
    入力
    13 117605741
    953112651 782347735
    616452546 593486619
    526409086 326024041
    871366520 70020328
    967605641 351333122
    313598854 695929004
    622500392 154948879
    218372422 180488451
    736384818 827380828
    944407248 833991038
    854462196 933316967
    593229348 385759804
    892532207 641219509
    出力
    774245621

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