問題一覧 > 通常問題

No.1938 Lagrange Sum

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 34
作問者 : noya2 / テスター : tatyam nok0 tassei903
お気に入りにしたユーザー ProblemId : 6856 / 自分の提出
問題文最終更新日: 2022-05-11 00:31:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 343 (順位表) の他の問題:

Problem Statement

You are given $N$ pairs of integers $(x_1,y_1), \dots ,(x_N,y_N)$.

For every $i$ satisfying $1\le i\le N$, define a polynomial $F_i(x)$ in $x$ of degree at most $N-2$ so that it satisfies the following.

  • $F_i(x_j)=y_j$ for every $j$ satisfying $1\le j\le N$ and $i\neq j$

    • Let $\displaystyle F(x)=\sum_{i=1}^{N} F_i(x)$. It can be shown that $F(X)$ is a rational number, so find it modulo $\bmod 998244353$.

    When printing a rational number, first represent it as a fraction $\frac{y}{x}$. Here, $x,y$ are integers, and $x$ must not be divisible by $998244353$ (under the constraints of this problem, such a representation is always possible). Then, print the unique integer $z$ between $0$ and $998244352$, inclusive, satisfying $xz\equiv y\ (\bmod 998244353)$.

    It can be proved that the answer is uniquely determined under the constraints of this problem.

    Constraints

  • All input values are integers
  • $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)$

    • Input

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

    Output

    Print $F(X)\ (\bmod 998244353)$ on $1$ line.

    Sample

    Sample 1
    Input
    3 3
0 0
1 1
2 4
    Output
    16

    We have $F_1(x)=3x-2,\ F_2(x)=2x,\ F_3(x)=x$.

    Since $F(x)=6x-2$, print $F(3)=16$.

    Sample 2
    Input
    6 15
9 6
15 14
10 15
1 0
2 8
3 17
    Output
    650

    Sample 3
    Input
    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
    Output
    774245621

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