链接:https://www.luogu.org/problemnew/show/P4781
思路:模板题,直接用公式暴力插就好,公式推导详情请看 https://www.luogu.org/problemnew/solution/P4781
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
using namespace std;
typedef long long ll; const int maxn = 2020; const ll mod = 998244353; int n, k; ll x[maxn], y[maxn], a[maxn], inv[maxn][maxn];
ll (ll q, ll w){ ll ret = 1; while(w){ if(w & 1) ret = ret * q % mod; q = q * q % mod; w >>= 1; } return ret; }
int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) cin >> x[i] >> y[i]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ inv[i][j] = pow_mod((x[i] - x[j]) % mod + mod, mod - 2); } } for(int i = 1; i <= n; i++){ a[i] = y[i]; for(int j = 1; j <= n; j++){ if(i == j) continue; a[i] = a[i] * inv[i][j] % mod; } } ll res = 0; for(int i = 1; i <= n; i++){ ll ans = a[i]; for(int j = 1; j <= n; j++){ if(i == j) continue; ans = ans * ((k - x[j]) % mod + mod) % mod; } res = (res + ans) % mod; } cout << res << 'n'; return 0; }
|
近期评论