問題一覧 > 通常問題

No.1938 Lagrange Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : noya2noya2 / テスター : 👑 tatyamtatyam nok0nok0 tassei903tassei903
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もしくは右上の雲マークをクリックしてアカウントを作成してください。