[数据结构与算法]【模板】智乃酱的静态数组维护问题多项式（多次差分数组——多项式处理）

题目

原题链接

问题描述

思路

差分数组的优点在于牵一发而动全身，通过处理一个位置便可以将后续位置的值都改变。

我们此时面临的操作是对区间处理，而且处理不是简单的加上某个值，而是对位于$[l,r]$中的$a[i]$加上$f(i)$，$f(i)$是一个最高阶数不超过$5$的多项式。

1.引入

在题目小W的糖果中，需要处理平方差分数组，也就是对于位置$l$以及其右侧的每个位置需要加上$i^2$，其实这也是一个特殊的多项式，我们通过进行$3$次差分：
$[1,4,9,16,25]?[1,3,5,7,9]?[1,2,2,2,2]?[1,1,0,0,0]$

在数学上，有一个结论：最高次项为$n$次的$n$阶多项式做$n+1$阶差分后余项为常数（非0项有限）。

依照这个定理，我们对一个序列上特定的位置加上特定的常数，再经过$n+1$次前缀和操作，就可以对位于$[l,+\infty )$中的$a[i]$加上最高次项为$n$次的$n$阶多项式$f(i)$。

值得注意的是，如果我们对最高次项为$n$次的$n$阶多项式做$n+2$阶差分，我们会得到什么样的结果呢？
依然使用上面的例子，再进行一次差分，我们将会得到序列$[1,0,?1,0,0]$，这个序列依然是一个非$0$项有限的序列。

此时又有了另一个问题，也就是这个非$0$项有限的序列的长度可能会在什么范围内，我们取$f(x)=x^5+x^4+x^3+x^2+x+6$来看看

$6$次差分后也就$6$项，所以我们一开始设定$10$位就可以推出这个序列了。

2.分析

但上述题目中的操作并不是对右侧全部元素进行操作，而是对区间$[l,r]$内部元素进行操作，所以我们需要对$[r+1,+\infty )$中的每个元素进行修正，此时也就是对这一段的每个元素加上$?f(i)$，依然可以将$?f(i)$视作是一个多项式，经过多次差分得到一个非$0$项有限的序列。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod =1e9+7;
const int N =1e5+7;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
ll t,n,m,q,a[N],l,r,k,c[15],p[2][15];
ll f(ll x, ll a[],ll k){
	ll res = 0;
	ll base = 1;
	fir(i,0,k){
		(res+=base*c[i])%=mod;
		(base*=x)%=mod;
	}
	return res;
}
ll g(ll x,ll a[],ll k,ll l,ll r){
	return (mod-f(x+r-l+1,a,k))%mod;
}
void P(ll a[], int len, int cnt){
	while(cnt--){
		fir(i,1,len){
			(a[i]+=a[i-1])%=mod;
		}
	}
}
void D(ll a[], int len, int cnt){
	while(cnt--){
		rif(i,len,0){
			a[i]=(a[i]-a[i-1]+mod)%mod;
		}
	}
}
int main(){
	scanf("%lld %lld %lld", &n, &m, &q);
	fir(i,1,n)scanf("%lld", &a[i]);
	D(a,n,6);
	while(m--){
		cin>>l>>r>>k;
		rif(i,k,0)scanf("%lld", &c[i]);
		fir(i,1,10){
			p[0][i]=f(i,c,k);
			p[1][i]=g(i,c,k,l,r);
		}
		D(p[0],10,6);
		D(p[1],10,6);
		fir(i,1,10){
			(a[l+i-1]+=p[0][i])%=mod;
			(a[r+i]+=p[1][i])%=mod;
		}
	}
	P(a,n,7);
	while(q--){
		scanf("%lld %lld", &l, &r);
		printf("%lld\n",((a[r]-a[l-1])%mod+mod)%mod);
	}
}