結果
問題 | No.1938 Lagrange Sum |
ユーザー |
![]() |
提出日時 | 2022-05-13 23:15:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 870 ms / 3,000 ms |
コード長 | 1,298 bytes |
コンパイル時間 | 3,877 ms |
コンパイル使用メモリ | 254,956 KB |
最終ジャッジ日時 | 2025-01-29 07:34:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main(){ int N,X; cin>>N>>X; vector<int> x(N),y(N); rep(i,N)cin>>x[i]>>y[i]; vector<mint> V(N); int ind = -1; rep(i,N){ V[i] =X-x[i]; if(V[i].val()!=0)V[i] = V[i].inv(); else ind = i; } mint ans = 0; if(ind == -1){ rep(i,N){ mint P = 1,Q = 1; rep(j,N){ if(i==j)continue; P *= X-x[j]; Q *= x[i]-x[j]; } P /= Q; Q = 0; rep(j,N){ if(i==j)continue; mint t = x[i]-x[j];//X-x[j]; t *= V[j];///= X-x[j]; Q += t; } P *= Q; P *= y[i]; ans += P; } } else{ rep(i,N){ if(i!=ind){ mint P = 1,Q = 1; rep(j,N){ if(j==ind||j==i)continue; P *= X-x[j]; Q *= x[i]-x[j]; } P /= Q; P *= y[i]; ans += P; } else{ mint P = 1,Q = 1; rep(j,N){ if(i==j)continue; P *= X-x[j]; Q *= x[i]-x[j]; } P /= Q; Q = 0; rep(j,N){ if(i==j)continue; mint t = x[i]-x[j];//X-x[j]; t *= V[j];///= X-x[j]; Q += t; } P *= Q; P *= y[i]; ans += P; } } } cout<<ans.val()<<endl; return 0; }