p4781

链接: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;
}