知识预备

多项式差分

对于一个多项式函数,定义它在x的一阶向前差分为,定义它在x的一阶向后差分为。

定义k阶向前差分：，
定义k阶向后差分：，
定义0阶差分：

多项式差分的性质

(C为常数)；


若,为最高次项系数为a_0的n次多项式，则
若,为n次多项式，则
若，则表示f(x)是一个次数小于等于r的代数多项式(为恒等号，表示全为0)

数组的前缀和以及差分

对于一个数组a定义数组为a数组的前缀和数组，定义数组为a数组的差分数组。
前缀和与差分运算为互逆运算，任意一个数组a的前缀和数组的差分数组是它本身。
长度大小为n的数组做前缀和运算可以视为是与一个长度大小为n的全1数组做卷积运算，这样前缀和运算所对应的生成函数为：
长度大小为n的数组做差分运算可以视为与数组做卷积运算，这样差分运算所对应的生成函数为：1-x
前缀和运算与差分运算对应生成函数互为卷积逆元，从卷积的角度讲他们也是互逆的。

静态维护区间加多项式的求和问题

现在有这么一类问题，给一个数组a进行若干次操作，每次操作的时候选定一个区间l,r和一个k次多项式,然后让你给a[l]加上,a[l+1]加上...，a[l+i]加上一直到a[r]加上。
进行完m次操作以后让你输出整个数组每个位置的值。
然后这类问题还是挺常见的（并没有），说实话，静态区间加等差数列还是挺常见的。
等差数列也可以看成是一个的多项式函数，所以也是可以做的。
那这类问题怎么解决呢，例如现在给你一个大小为10的数组让你对区间3~5加上一个多项式。
可以利用的性质，也就是n次多项式的n+1阶及以上差分自身的贡献为0,改为维护a数组的n+1阶差分数组，最后再做n+1阶前缀和运算还原回a数组。

具体过程

一、首先把的值填到一个大小为n+1的数组f中（n为多项式次数）。

如示例中的多项式，填入一个大小为3+1的数组中。
5 4 9 26

二、对数组f做n+1次差分运算

下标 0 1 2 3
f 5 4 9 26
d1 5 -1 5 17
d2 5
 -6
 6 12
d3 5 -11 12 6
d4 5
-16
23 -6
运算的结果为，我们把这部分内容填到需要维护的a数组中（从a[l]开始填）
下标 0 1 2 3 4 5 6 7 8 9
值 0 0 0 5 -16 23 -6 0 0 0
虽然现在只做了一半，但是如果现在对a数组做n+1次前缀和运算会有什么效果？
x 0 1 2 3 4 5 6 7 8 9
d4 0 0 0 5 -16 23 -6 0 0 0
d3 0 0 0 5 -11 12 6 6 6 6
d2
 0 0 0 5 -6 6 12 18 24 30
d1
 0 0 0 5 -1 5 17 35 59 89
a
 0 0 0 5 4 9 26 61 120 209
然后发现如果现在还原的话确实相当于给3这个下标以后的每个位置加上了这个多项式函数f(x)，但是没有处理右边界。

三、构造函数

这步构造在代码实现上就别真求g(x)的系数了，可以直接写 
int g(int x,int l,int r)
{
    return -f(x+r-l+1);
}
然后跟第二步中的做法一样，把的值填到一个大小为n+1的数组g中（n为多项式次数），然后做n+1次差分运算。

下标 0 1 2 3
g -26 -61 -120 -209
d1 -26 -35 -59 -89
d2 -26 -9 -24 -30
d3 -26 17 -15 -6
d4 -26 43 -32 9
运算的结果为，我们把这部分内容填到需要维护的a数组中（从a[r+1]开始填）
因为之前已经填过，这次填数是在上一次的基础上，上一次天数的结果也要保留，所以把他们加起来求和。
下标 0 1 2 3 4 5 6 7 8 9
值 0 0 0 5 -16 23 -6-26 43 -32 9
注意d4[6]这个位置，是-6-26，两次操作都对6这个位置有贡献。

四、做n+1次前缀和运算还原回a数组。

x 0 1 2 3 4 5 6 7 8 9
d4 0 0 0 5 -16 23 -32 43 -32 9
d3 0 0 0 5 -11 12 -20 23 -9 0
d2
 0 0 0 5 -6 6 -14 9 0 0
d1
 0 0 0 5 -1 5 -9 0 0 0
a
 0 0 0 5 4 9 0 0 0 0
当然，对于本题，比如限定好范围如多项式的次数,那就直接维护一个d11数组（意为a数组的11阶差分数组）
该算法的时间复杂度为

优化：快速差分，快速前缀和

上述算法的瓶颈在于k，无论是前缀和还是差分，都跟k脱不了关系，而且求前缀和与差分的方法就是暴力for。
但是无论是多项式差分的性质中有，还是我上面提到的差分与前缀和运算可以用卷积实现。
这都暗示你k阶差分与k阶前缀和可以用组合数+卷积的形式快速求的。
需要用到的知识预备：
1、O(1)快速组合数。
2、FFT/NTT/MTT至少学会一种卷积。
快速组合数以及卷积这个满大街都是，我就不说了，不会的话自行百度。

快速差分

卷积式：，限制条件是可以计算0阶差分（原数组）。
即

快速前缀和

卷积式：，限制条件是，不能计算0阶前缀和。
即

需要注意一下哈，当k=0时会出现组合数里面产生的现象，在求前缀和时最好特判掉0阶前缀和。

优化后的复杂度为,yysy啊，没感觉有多优秀。
如果是动态区间加多项式问题的话可用线段树维护多项式系数来实现。