连续的取点,时间复杂度\(O(n)\)
模板
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 60, MOD = 998244353;
int n, k, fac[N], inv[N], pows[N][N], x[N], y[N];
long long quickPower (long long x, long long y) {
long long res = 1;
while (y) {
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
int Lagrange (int n, int *x, int *y, int k) {
static int pre[N], suf[N];
int ans = 0;
pre[0] = k - x[0], suf[n + 1] = 1;
for (int i = 1; i <= n; i ++) pre[i] = 1ll * pre[i - 1] * (k - x[i]) % MOD;
for (int i = n; i >= 0; i --) suf[i] = 1ll * suf[i + 1] * (k - x[i]) % MOD;
for (int i = 0; i <= n; i ++) {
int up = 1ll * (i == 0 ? 1 : pre[i - 1]) * suf[i + 1] % MOD;
int down = 1ll * inv[i] * inv[n - i] % MOD * ((n - i & 1) ? MOD - 1 : 1) % MOD;
ans = (ans + 1ll * y[i] * up % MOD * down % MOD) % MOD;
}
return ans;
}
inline int C (int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int solve (int n, int k) {
int ans = 0;
for (int p = 1; p <= n; p ++)
for (int v = 1; v <= k; v ++) {
int x1 = v - 1, y1 = k - (v - 1), x2 = k - v, y2 = v;
for (int i = 0; i <= p - 1; i ++)
for (int j = i + 1; j <= n - p; j ++)
ans = (ans + 1ll * v * C(p - 1, i) % MOD * C(n - p, j) % MOD * pows[x1][i] % MOD * pows[y1][p - 1 - i] % MOD * pows[x2][j] % MOD * pows[y2][n - p - j] % MOD) % MOD;
}
return ans;
}
int main () {
scanf("%d%d", &n, &k);
fac[0] = inv[0] = 1;
for (int i = 1; i <= 55; i ++) {
fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[i] = quickPower(fac[i], MOD - 2);
}
for (int i = 0; i <= 55; i ++)
for (int j = 0; j <= 55; j ++) {
if (!j) pows[i][j] = 1;
else pows[i][j] = 1ll * pows[i][j - 1] * i % MOD;
}
if (k <= n + 2) {
printf("%d\n", solve(n, k));
return 0;
}
for (int i = 0; i <= n + 2; i ++) {
x[i] = i;
y[i] = solve(n, i);
}
printf("%d\n", Lagrange(n + 2, x, y, k));
return 0;
}
非连续的取点,时间复杂度\(O(n ^ 2)\)
模板
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2010, MOD = 998244353;
int n, k, x[N], y[N];
long long quickPower (long long x, long long y) {
long long res = 1;
while (y) {
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
int Lagrange (int n, int *x, int *y, int k) {
int ans = 0;
for (int i = 0; i <= n; i ++) {
int inv = 1, res = 1;
for (int j = 0; j <= n; j ++)
if (j != i) {
inv = 1ll * inv * ((x[i] - x[j] + MOD) % MOD) % MOD;
res = 1ll * res * ((k - x[j] + MOD) % MOD) % MOD;
}
inv = quickPower(inv, MOD - 2);
ans = (ans + 1ll * y[i] * res % MOD * inv % MOD) % MOD;
}
return ans;
}
int main () {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++)
scanf("%d%d", &x[i], &y[i]);
printf("%d\n", Lagrange(n - 1, x, y, k));
return 0;
}
标签:拉格朗,suf,插值,res,long,int,include,MOD
From: https://www.cnblogs.com/duoluoluo/p/17011565.html