結果

問題 No.1938 Lagrange Sum
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:04:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 703 ms / 3,000 ms
コード長 2,536 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 79,312 KB
最終ジャッジ日時 2025-04-09 21:06:16
合計ジャッジ時間 10,660 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def modinv(a):
    return pow(a, MOD-2, MOD)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, X = int(input[idx]), int(input[idx+1])
    idx +=2
    x = []
    y = []
    for _ in range(N):
        a = int(input[idx])
        b = int(input[idx+1])
        x.append(a)
        y.append(b)
        idx +=2
    
    # Check if X is in x
    is_x_present = False
    p = -1
    for i in range(N):
        if x[i] == X:
            is_x_present = True
            p = i
            break
    if is_x_present:
        # Handle special case
        total = (N-1) * y[p] % MOD
        # Compute sum over j != p: y_j * product_{m != j,p} (x_p -x_m)/(x_j -x_m)
        sum_extra = 0
        x_p = X
        for j in range(N):
            if j == p:
                continue
            numerator = 1
            denominator = 1
            for m in range(N):
                if m == p or m == j:
                    continue
                numerator = numerator * (x_p - x[m]) % MOD
                denominator = denominator * (x[j] - x[m]) % MOD
            term = y[j] * numerator % MOD
            term = term * modinv(denominator) % MOD
            sum_extra = (sum_extra + term) % MOD
        total = (total + sum_extra) % MOD
        print(total)
        return
    
    # General case, X is not in x
    # Precompute X -x_i and inv_denom
    inv_denom = []
    for xi in x:
        d = (X - xi) % MOD
        if d == 0:
            inv_denom.append(0)
        else:
            inv_denom.append(modinv(d))
    
    S_total = sum(inv_denom) % MOD
    
    # Precompute product (X - x_i) for all i
    GX = 1
    for xi in x:
        GX = GX * (X - xi) % MOD
    
    # Precompute denominator[k] for each k: product_{m!=k} (x_k - x_m)
    denominator = [1]*N
    for k in range(N):
        den = 1
        for m in range(N):
            if m == k:
                continue
            den = den * (x[k] - x[m]) % MOD
        denominator[k] = den
    
    result = 0
    for k in range(N):
        # Compute C(k) = GX / ((X -x[k]) * denominator[k])
        denom = denominator[k]
        term_denom = (X - x[k]) % MOD
        term_denom = (term_denom * denom) % MOD
        Ck = GX * modinv(term_denom) % MOD
        
        sum_i = (S_total - inv_denom[k]) % MOD
        Tk = ( (N-1) - ( (X - x[k]) % MOD ) * sum_i ) % MOD
        Sk = Ck * Tk % MOD
        term = y[k] * Sk % MOD
        result = (result + term) % MOD
    
    print(result % MOD)

if __name__ == '__main__':
    main()
0