智乃酱的静态数组维护问题多项式（拉格朗日插值求高阶差分）

本文主要是介绍智乃酱的静态数组维护问题多项式（拉格朗日插值求高阶差分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

智乃酱的静态数组维护问题多项式

题目大意

有 $n$ 个数 $\cdots, a[n]$ .

$m$ 次操作，每次操作给出一个多项式函数 $\begin{aligned} \sum_{i=0}^{k}{c_ix^i} \end{aligned}$ 和区间 $[l, r]$ 表示进行操作 $\; i \in [l, r]$ .

$m$ 次操作之后进行 $q$ 次询问，每次查询区间 $[l, r]$ 的和.

$\leq n, m, q \leq 10^5 , 0 \leq a[i], c_i \leq 10^9, 0 \leq k \leq 5, 1 \leq l \leq r \leq n$ .

分析

可以把多项式函数 $f (x)$ 按照 $x^i$ 拆开分别考虑.

对每个 $x^i$ 做 $6$ 次差分，记差分数组为 $d$ ，不难发现 $\cdots, d[l + 5], d[r + 1], d[r + 2], \cdots, d[r + 6]$ 是关于 $r - l + 1$ 的 $5$ 次多项式函数，该函数可通过拉格朗日插值求得.

详见代码.

代码实现

#include <bits/stdc++.h>
using namespace std;template <typename T>
void read(T& n)
{n = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while( isdigit(ch)) {n = n * 10 + ch - '0', ch = getchar();}n *= f;
}template <typename T>
void print(T n)
{if(n < 0) putchar('-'), n = -n;if(n > 9) print(n / 10);putchar(n % 10 + '0');
}template <typename T>
void print(T n, char ch)
{print(n), putchar(ch);
}typedef long long ll;const int M = (int)1e5;
const int N = (int)5;
const double eps = 1e-6;
const int mod = (int)1e9 + 7;
const int inf = 0x3f3f3f3f;int n, m, q;
int a[M + 5];
int b[N + 2][3 * N + 3];
int y[N + 1][2 * N + 3][N + 2];
int d[M + 5];
int pre[N + 3], suf[N + 3];
int fac[N + 1], inv[N + 1], facinv[N + 1];ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s % p;
}void init()
{fac[0] = facinv[0] = fac[1] = inv[1] = facinv[1] = 1;for(int i = 2; i <= N; ++i){fac[i] = 1ll * fac[i - 1] * i % mod;inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;facinv[i] = 1ll * facinv[i - 1] * inv[i] % mod;}for(int i = 0; i <= N; ++i){for(int j = 2 * N + 2; j <= 3 * N + 2; ++j){for(int k = 1; k <= j - N - 1; ++k) b[0][k] = quick(k, i);for(int k = j - N; k <= j; ++k) b[0][k] = 0;for(int k = 1; k <= N + 1; ++k){for(int l = 1; l <= j; ++l) b[k][l] = b[k - 1][l] - b[k - 1][l - 1];}for(int k = 1; k <= N + 1; ++k) y[i][k][j - 2 * N - 1] = b[N + 1][k];for(int k = j - N; k <= j; ++k) y[i][k - j + 2 * N + 2][j - 2 * N - 1] = b[N + 1][k];}}
}int L(int y[], int x)
{if(1 <= x && x <= N + 1) return y[x];pre[0] = 1; for(int i = 1; i <= N; ++i) pre[i] = 1ll * pre[i - 1] * (x - i) % mod;suf[N + 2] = 1; for(int i = N + 1; i >= 0; --i) suf[i] = 1ll * suf[i + 1] * (x - i) % mod;int s = 0, cur;for(int i = 1; i <= N + 1; ++i){cur = 1ll * pre[i - 1] * suf[i + 1] % mod;cur = 1ll * cur * facinv[i - 1] % mod * facinv[N + 1 - i] % mod;if((N + 1 - i) & 1) cur = -cur;cur = 1ll * cur * y[i] % mod;(s += cur) %= mod;}return s;
}void dif(int k, int c, int l, int r)
{for(int i = 1; i <= N + 1; ++i)  (d[i + l - 1] += 1ll * L(y[k][i], r - l + 1 - N) * c % mod) %= mod;for(int i = N + 2; i <= 2 * N + 2; ++i) (d[i - N + r - 1] += 1ll * L(y[k][i], r - l + 1 - N) * c % mod) %= mod;
}void work()
{read(n), read(m), read(q);for(int i = 1; i <= n; ++i) read(a[i]), (a[i] += a[i - 1]) %= mod;for(int i = 1, l, r, k, c; i <= m; ++i){read(l), read(r), read(k);for(int j = k; j >= 0; --j){read(c);dif(j, c, l, r);}}for(int i = N + 1; i >= 0; --i){for(int j = 1; j <= n; ++j) (d[j] += d[j - 1]) %= mod;}for(int i = 1, l, r, s; i <= q; ++i){read(l), read(r);(s = a[r] - a[l - 1]) %= mod;(s += (d[r] - d[l - 1]) % mod) %= mod;print((s % mod + mod) % mod, '\n');}
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
        printf("Case #%d:", ca);
//        work();
//    }init();work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}