首页 > 其他分享 >[ABC137F] Polynomial Construction 题解

[ABC137F] Polynomial Construction 题解

时间:2024-09-07 10:25:22浏览次数:13  
标签:vector int 题解 多项式 ++ Construction res Polynomial mod

明明有最厉害最好想的插值做法,怎么没有人写呢。

思路

考虑 \(n\) 个点可以确定一个 \(n-1\) 次多项式。

如何确定。

令 \(l_i(x)=\prod_{j\not =i}\frac{(x-x_j)}{(x_i-x_j)}\)。

可以发现这个多项式在 \(x=x_i\) 时值为一,在 \(x=x_j(j\not = i)\) 时值为零。

那么就有:

\[F(x)=\sum_{i=0}^{i<n}y_il_i(x) \]

容易发现这个多项式恰好满足上面的条件,当然,这就是拉格朗日插值。

如何得到这个多项式?

可以先求出:

\[G(x)=\prod(x-x_i) \]

发现:

\[l_i(x)=\frac{G(x)}{(x-x_i)k_i} \]

其它的是一个常数所以和起来写成 \(k_i\) 即可。

那么就可以 \(O(n^2)\) 求解了。

思路

#include <bits/stdc++.h>
using namespace std;

#define int long long

int mod;

inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = res * x % mod;
    x = x * x % mod, y /= 2;
  }
  return res;
}

inline vector<int> lagrange(const vector<int> &x, const vector<int> &y) {
  int n = x.size();
  vector<int> a(n + 1, 0), f(n, 0);
  a[0] = 1;
  auto add = [&](int x) {
    for (int j = n; j >= 1; j--)
      a[j] = (a[j - 1] - a[j] * x) % mod;
    a[0] = -a[0] * x % mod;
  };
  for (int i = 0; i < n; i++) add(x[i]);
  for (int i = 0; i < n; i++) {
    if (x[i] == 0) {
      for (int j = 0; j <= n; j++) a[j] = a[j + 1];
      a[n] = 0;
    } else {
      int iv = power(x[i], mod - 2);
      a[0] = -a[0] * iv % mod;
      for (int j = 1; j <= n; j++) {
        a[j] = a[j] - a[j - 1];
        a[j] = -a[j] * iv % mod;
      }
    }
    int s = 1;
    for (int j = 0; j < n; j++)
      if (i != j) s = s * (x[i] - x[j]) % mod;
    s = power(s, mod - 2) * y[i] % mod;
    for (int j = 0; j < n; j++)
      f[j] = (f[j] + a[j] * s) % mod;
    add(x[i]);
  }
  for (int i = 0; i < n; i++) f[i] = (f[i] % mod + mod) % mod;
  return f;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);

  vector<int> a, b, f;

  cin >> mod;
  for (int i = 1, x; i <= mod; i++) {
    cin >> x;
    a.push_back(i - 1);
    b.push_back(x);
  }
  f = lagrange(a, b);
  for (int i = 0; i < mod; i++)
    cout << f[i] << " \n"[i == mod - 1];

  return 0;
}

标签:vector,int,题解,多项式,++,Construction,res,Polynomial,mod
From: https://www.cnblogs.com/JiaY19/p/18401399

相关文章

  • 洛谷 P3034 Cow Photography G/S——题解
    洛谷P3034题解传送锚点摸鱼环节[USACO11DEC]CowPhotographyG/S题面翻译题目描述今天的奶牛们特别调皮!FarmerJohn想做的只是给排成一排的奶牛拍照,但是在他拍下照片之前,奶牛们一直在移动。具体地说,FJ有\(N\)头奶牛(\(1\leqN\leq20\,000\)),每头奶牛都有一个唯一确......
  • 题解:AT_abc369_e [ABC369E] Sightseeing Tour 详细版
    题目大意给定一个NNN个点,MMM条边的无向图。其中边有边权。有......
  • MySQL 日期函数语法介绍和案例示范以及常见问题解决
    本文将以电商交易系统为例,详细讲解MySQL日期类型及其转化,常用的日期函数,以及一些解决常见问题的方案。一、MySQL日期数据类型MySQL提供了多种日期数据类型,适用于不同的使用场景。常见的日期类型包括DATE、DATETIME、TIMESTAMP、TIME和YEAR。DATE:只存储日期,不包含......
  • 题解:SP3693 KGSS - Maximum Sum
    原题传送门思路分析线段树。这道题让我们进行两种操作,分别是单点修改和区间查询,结合数据范围,很明显是一道线段树。区间里最大的\(A_i+A_j\),其实就是求区间里的最大值和次大值,我们用线段树维护最大值和次大值。建树voidbuild(intnow,inttl,inttr){ if(tl==tr){ tmax......
  • P6638 「JYLOI Round 1」常规 题解
    题目传送门前置知识可持久化线段树|前缀和&差分解法进行差分,区间查询转化成前缀和相减。先将\(\{a\}\)升序排序。设当前询问的区间为\([1,r]\),在\(\{a\}\)中找到一个最大的\(pos\)使得\(a_{pos}\ler\),则\([1,r]\)中所做常规的次数为\(\sum\limits_{i=1......
  • 使用flask进行Mock Server模拟接口操作及问题解决
    1.flask介绍flask是一个轻量级的pythonweb微框架2.MockServer介绍MockServer是一个开源的模拟服务器,它可以定义和记录API交互,支持各种http方法(get、post、put、delete),可以自定义响应内容,例如返回静态文件可以使用flask来搭建一个mock模拟服务3.模拟接口先安装flaskpip......
  • P1928 外星密码题解
    初看这题时,感觉就是一个简简单单的递归,便有了以下代码:#include <bits/stdc++.h>using namespace std;string re(){    string s="",s1="";    char c;    int n;    while(cin>>c){        if(c=='['){            cin>>n;......
  • AT_keyence2019_e Connecting Cities 题解
    B算法萌萌题。题解看到完全图求最小生成树,必然是要考虑一下B算法能不能做的。发现这个题的联通块最小值是可以维护的。我们发现。假如我们钦定\(i\)往前面连。那么前面的最小权值必然是一个固定的值。我们一定会连到\(\min(a_j-j\timesD)\)上。由于不能连到自己......
  • AT_aising2019_e Attack to a Tree 题解
    挺有意思的树型dp。思路发现直接求解很难对限制下手。但我们可以注意到答案最多为\(n\)。考虑将答案记录dp状态。我们可以记\(dp_{i,j}\)为子树\(i\)合法并且断了\(j\)条边的状态。由于合法状态有两种,并且不好一起考虑,所以可以再在dp状态中加一维。令\(dp_{i,......
  • P8139 [ICPC2020 WF] Sweep Stakes 题解
    思路容易发现,题目要求我们动态维护这样一个多项式。\[\prod_{i}(1-p_i+p_ix)\]如何维护。由于精度问题,我们很难去进行一个多项式除法将其暴力求出。考虑\(p_i\le0.2\)。可以得知,我们的多项式的数的增减是比较大的。那么在一定数量后,一些可能有值的系数在当前精度下是可以......