给你 n 个点 , 第i个点的坐标为(xi , yi)
一定会有一个L[X] 满足:经过这 n 个点
也就是: 对于任意一个xi,必定会有L[xi] = yi
设L[x] = y[1] * l1[x] + y[2] * l2[x] + ... + y[i] * l3[x] + .... + y[n] * ln[x]
其中:
这样:当x = xi , l(x != xi )[x] = 0,因为一定有一项 (xi - xi)为 0 , 连乘后也为 0 , 最后就只剩下 li[x] 这项不为0 , 且在把x = xi 带入 li[x] 的时候 ,上下可以约掉 ,最后li[x] = 1 , L[xi] = yi , 且可以满足所有的点.
代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10; #define ll long long #define int long long #define ios std::ios::sync_with_stdio(false) const ll INF(0x3f3f3f3f3f3f3f3fll); const int inf(0x3f3f3f3f); ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}//xµÄn´Î·½mod template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} const int mod = 998244353; struct node { int x , y; }; node p[maxn]; signed main() { ios; cin.tie(0); int n , k; cin >> n >> k; for(int i = 1 ; i <= n ; i ++) cin >> p[i].x >> p[i].y , p[i].x %= mod , p[i].y %= mod; int ans = 0; for(int i = 1 ; i <= n ; i ++){ int vv = 1; for(int j = 1 ; j <= n ; j ++){ if(i == j) continue; vv *= (k - p[j].x + mod) % mod , vv %= mod; vv *= (pow_mod(p[i].x - p[j].x , mod - 2 , mod) + mod) % mod , vv %= mod; } vv *= ((p[i].y + mod)% mod) , vv %= mod; ans += vv % mod , ans %= mod; } cout << ans % mod << '\n'; return 0; }