首页 > 其他分享 >拉格朗日插值

拉格朗日插值

时间:2022-12-29 00:11:16浏览次数:58  
标签:拉格朗 suf 插值 res long int include MOD

连续的取点,时间复杂度\(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

相关文章

  • 数值分析·学习 | 拉格朗日插值法matlab实现
    ​目录前言一、拉格朗日(Lagrange)插值是什么?二、matlab实现代码1.线性插值:2.抛物线插值:3.拉格朗日(Lagrange)插值:总结:前言本篇内容为个人所学知识分享一、拉格朗......
  • 数值分析·学习 | 牛顿插值法matlab实现
     目录前言一、牛顿插值法是什么?1.均差下的牛顿插值2.为了给出​编辑的表达式,引入均差的概念3.差分形式的牛顿插值公式(牛顿前插公式)三、matlab实现代码1.生成牛顿均......
  • 拉格朗日插值求系数
    拉格朗日插值求系数设有\(n\)个点,坐标为\((x_i,y_i)\),现在要求解它们所够成的\(n-1\)次多项式\(F(x)\)的系数.先回顾一下一般拉格朗日插值:定义\[f_i(x)=\begin{case......
  • 拉格朗日反演学习记录
    \(\texttt{updating……}\)多项式复合对于多项式\(F(x),G(x)\),其复合为:\(F(G(x))=\sum_{i}[x^i]F(x)G(x)^i\)求法:设\(B=\sqrtn\)\[\begin{aligned}\sum_{i=0}^n[x......
  • 图像处理——双三次插值算法
    参考论文:[1]李英民.图像双三次插值算法的研究[D].兰州大学,2020.DOI:10.27204/d.cnki.glzhu.2020.000657.......
  • ENVI 5.6.2 及以上版本默认显示插值方法说明
    在ENVI5.6.2版本新特性中有一项是:ChangedtheZoomInterpolationMethoddefaultpreferenceOptimizedBicubic更改了“缩放插值方法”默认选项为“优化双三次”......
  • Cesium实时轨迹、点击运动、插值坐标、轨迹回放
    老规矩,效果图放前面,满足需求接着往下看。加载模型模型加载方式为primitive,利用矩阵设置世界坐标,modelMatrix,包含位置方向,在此基础上可以做到物体位移。letPrimitive:......
  • 验证darknet中前处理做图像缩放(双线性内插值法)scale的算法效果
    ​​DARKNET中使用的缩放算法是双线性内插值法,这里就实际验证一把DARKNET中scale的工作原理与效果:首先这是一张原图,画面中的是南京明城墙玄武门,玄武湖的正门。18年国庆带娃......
  • 第五章 插值与逼近
    5.1离散问题定义给定一组点\(\{x_i,y_i\}\quad(i=0,1,\cdots,n)\)并且\(x_0<x_1<\cdots<x_n\),若函数\(f(x)\)使得\(\qquadf(x_i)=y_i\quad(i=0,1,\cdots,n)\)成立,则......
  • 使用Matlab进行图像的读写、显示和缩放(最近临插值和双线性内插值法)
    上次我们开始进行数字图像处理这门课程的实验,直到现在才抽空出来写写文章,记录一下知识点。介绍一下,使用Matlab对数字图像的简单处理。1、 读取与显示输入图像:%输入图像和显......