差分的定义

定义 f(x)4f(x)4 的差分（向后差） ∇f(x)\nabla f(x) ：

∇f(x)=f(x)−f(x−1)\nabla f(x)=f(x)-f(x-1)

则有：

∇2f(x)=∇(∇f(x))=∇(f(x)−f(x−1))=f(x)−f(x−1)−[f(x−1)−f(x−2)]=f(x)−2f(x−1)+f(x−2)…\begin{aligned} \nabla^{2}f(x) &=\nabla(\nabla f(x)) \\ \\ &=\nabla ( f(x)-f(x-1) ) \\\\&=f(x)-f(x-1)-[f(x-1)-f(x-2)] \\\\&=f(x)-2f(x-1)+f(x-2) \end{aligned}\\ \dots

等等，因此称 ∇nf(x)\nabla^{n}f(x) 为 f(x)f(x) 的 nn 阶差分,

并且 ∇0f(x)=f(x)\nabla^{0}f(x)=f(x)。

差分与级数部分和的联系
首先有个比较明显的关系：

∇n+1f(x)=∇nf(x)−∇nf(x−1)\nabla^{n+1}f(x)= \nabla^{n}f(x)- \nabla^{n}f(x-1)

再结合级数部分和的公式:

f(x)=∑a=1x[f(a)−f(a−1)]+f(0)f(x)=\sum_{a=1}^{x}[f(a)-f(a-1)]+f(0)

就得到:

∇nf(x)=∑a=1x[∇nf(a)−∇nf(a−1)]+∇nf(0)=∑a=1x∇n+1f(a)+∇nf(0)\begin{aligned} \nabla^{n}f(x)&=\sum_{a=1}^{x}[\nabla^{n}f(a)-\nabla^{n}f(a-1)] +\nabla^{n}f(0) \\&=\sum_{a=1}^{x}\nabla^{n+1}f(a) +\nabla^{n}f(0) \end{aligned}

用上面的式子不断递归，并记 cn=∇nf(0)c_{n}=\nabla^{n}f(0)：

∇nf(x)=[∑a=1x∇n+1f(a)]+cn=[∑a=1x[∑b=1a∇n+2f(b)]+cn+1]+cn=[∑a=1x[∑b=1a[∑c=1b[∑d=1c∇n+4f(d)]+cn+3]+cn+2]+cn+1]+cn⋅⋅⋅⋅⋅⋅\begin{aligned}\nabla^{n}f(x)&=[\sum_{a=1}^{x}\nabla^{n+1}f(a)]+c_{n} \\&=[\sum_{a=1}^{x}[\sum_{b=1}^{a}\nabla^{n+2}f(b)] +c_{n+1}] +c_{n} \\&=[\sum_{a=1}^{x}[\sum_{b=1}^{a}[\sum_{c=1}^{b}[\sum_{d=1}^{c}\nabla^{n+4}f(d)] +c_{n+3}] +c_{n+2}] +c_{n+1}] +c_{n} \\\\&······ \end{aligned}

然后我们总结下上面发生的关系，并且把后面的常数尾巴提炼出来，写成多项式 ：

∇nf(x)=[∑a=1x∑b=1a∑c=1b⋅⋅⋅∑q=1m⏟s个 ∇n+sf(q)]+c(x)\nabla^{n}f(x)=[\underbrace{\sum_{a=1}^{x}\sum_{b=1}^{a}\sum_{c=1}^{b}···\sum_{q=1}^{m}}_\text{s个 } \nabla^{n+s}f(q)]+c(x)

令 n=−sn=-s ： ∇−sf(x)=[∑a=1x∑b=1a∑c=1b⋅⋅⋅∑q=1m⏟s个 ∇0f(q)]+c(x)=[∑a=1x∑b=1a∑c=1b⋅⋅⋅∑q=1m⏟s个 f(q)]+c(x)\begin{aligned}\nabla^{-s}f(x)&=[\underbrace{\sum_{a=1}^{x}\sum_{b=1}^{a}\sum_{c=1}^{b}···\sum_{q=1}^{m}}_\text{s个 }\nabla^{0}f(q)]+c(x) \\&=[\underbrace{\sum_{a=1}^{x}\sum_{b=1}^{a}\sum_{c=1}^{b}···\sum_{q=1}^{m}}_\text{s个 }f(q)]+c(x) \end{aligned}

可以看出负数阶差分相当于正数阶求和，求和是差分的逆运算。

多项式证明

对一个数列 {an}\{a_n\}，把元素两两做差，得到数列 {bn}\{b_n\} ，那么 {bn}\{b_n\} 就是 {an}\{a_n\}的阶差数列，记数列 {bn}\{b_n\} 为数列 {an}\{a_n\} 的一阶差分，记作 ∇f(x)=f(x)−f(x−1)\nabla{f(x)}=f(x)-f(x-1)。

同理高阶同上，即 ∇pf(x)=∇(∇p−1f(x))\nabla^p{f(x)}=\nabla(\nabla^{p-1}f(x))。

注：差分之后元素个数是会依次减少的。

pp 阶等差数列定义：若 {an}\{a_n\} 的 pp 阶差分为非 00 常数数列，那么称它为它的 pp 阶等差数列。

可以证明 S(n)=∑i=1nikS(n)=\sum_{i=1}^ni^k，其中 kk 为常数，为多项式。

以下借助 oi−wikioi-wiki

差分法

差分法适用于 xi=ix_i=i 的情况。

如，用差分法求某三次多项式 f(x)=∑i=03aixif(x)=\sum_{i=0}^{3} a_ix^i 的多项式形式，已知 f(1)f(1) 至 f(6)f(6) 的值分别为 1,5,14,30,55,911, 5, 14, 30, 55, 91。

15143055914916253657911222\begin{array}{cccccccccccc} 1 & & 5 & & 14 & & 30 & & 55 & & 91 & \\ & 4 & & 9 & & 16 & & 25 & & 36 & \\ & & 5 & & 7 & & 9 & & 11 & \\ & & & 2 & & 2 & & 2 & \\ \end{array}

第一行为 f(x)f(x) 的连续的前 nn 项；之后的每一行为之前一行中对应的相邻两项之差。观察到，如果这样操作的次数足够多（前提是 f(x)f(x) 为多项式），最终总会返回一个定值。

计算出第 i−1i-1 阶差分的首项为 ∑j=1i(−1)i+j(i−1j−1)f(j)\sum_{j=1}^{i}(-1)^{i+j}\binom{i-1}{j-1}f(j)，第 i−1i-1 阶差分的首项对 f(k)f(k) 的贡献为 (k−1i−1)\binom{k-1}{i-1} 次。

f(k)=∑i=1n(k−1i−1)∑j=1i(−1)i+j(i−1j−1)f(j)f(k)=\sum_{i=1}^n\binom{k-1}{i-1}\sum_{j=1}^{i}(-1)^{i+j}\binom{i-1}{j-1}f(j)

时间复杂度为 O(n2)O(n^2)。这种方法对给出的点的限制性较强。

待定系数法

设 f(x)=∑i=0n−1aixif(x)=\sum_{i=0}^{n-1} a_ix^i 将每个 xix_i 代入 f(x)f(x)，有 f(xi)=yif(x_i)=y_i，这样就可以得到一个由 nn 条 nn 元一次方程所组成的方程组，然后使用 高斯消元 解该方程组求出每一项 aia_i，即确定了 f(x)f(x) 的表达式。

时间复杂度 O(n3)O(n^3)，对给出点的坐标无要求。

拉格朗日插值

f(x)=∑i=1nyi∏j≠ix−xjxi−xjf(x)=\sum_{i=1}^n{y_i\prod_{j\ne i}{\dfrac {x-x_j}{x_i-x_j}}}

这就是拉格朗日插值的表达式。

本题中，还需要求解逆元。如果先分别计算出分子和分母，再将分子乘进分母的逆元，累加进最后的答案，时间复杂度的瓶颈就不会在求逆元上，时间复杂度为 O(n2)O(n^2)。

横坐标是连续整数的拉格朗日插值

如果已知点的横坐标是连续整数，我们可以做到 O(n)O(n) 插值。

设要求 nn 次多项式为 f(x)f(x)，我们已知 f(1),⋯ ,f(n+1)f(1),\cdots,f(n+1)（1≤i≤n+11\le i\le n+1），考虑代入上面的插值公式：

f(x)=∑i=1n+1yi∏j≠ix−xjxi−xj=∑i=1n+1yi∏j≠ix−ji−j\begin{aligned} f(x)&=\sum\limits_{i=1}^{n+1}y_i\prod\limits_{j\ne i}\frac{x-x_j}{x_i-x_j}\\ &=\sum\limits_{i=1}^{n+1}y_i\prod\limits_{j\ne i}\frac{x-j}{i-j} \end{aligned}

后面的累乘可以分子分母分别考虑，不难得到分子为：

∏j=1n+1(x−j)x−i\dfrac{\prod\limits_{j=1}^{n+1}(x-j)}{x-i}

分母的 i−ji-j 累乘可以拆成两段阶乘来算：

(−1)n+1−i⋅(i−1)!⋅(n+1−i)!(-1)^{n+1-i}\cdot(i-1)!\cdot(n+1-i)!

于是横坐标为 1,⋯ ,n+11,\cdots,n+1 的插值公式：

f(x)=∑i=1n+1yi⋅∏j=1n+1(x−j)(x−i)⋅(−1)n+1−i⋅(i−1)!⋅(n+1−i)!f(x)=\sum\limits_{i=1}^{n+1}y_i\cdot\frac{\prod\limits_{j=1}^{n+1}(x-j)}{(x-i)\cdot(-1)^{n+1-i}\cdot(i-1)!\cdot(n+1-i)!}

预处理 (x−i)(x-i) 前后缀积、阶乘阶乘逆，然后代入这个式子，复杂度为 O(n)O(n)。

CF622F The Sum of the k-th Powers

f(x)=∑i=1n+1(x−1i−1)∑j=1i(−1)i+j(i−1j−1)yj=∑i=1n+1yi⋅∏j=1n+1(x−j)(x−i)⋅(−1)n+1−i⋅(i−1)!⋅(n+1−i)!f(x)=\sum_{i=1}^{n+1}\binom{x-1}{i-1}\sum_{j=1}^{i}(-1)^{i+j}\binom{i-1}{j-1}y_{j}=\sum\limits_{i=1}^{n+1}y_i\cdot\frac{\prod\limits_{j=1}^{n+1}(x-j)}{(x-i)\cdot(-1)^{n+1-i}\cdot(i-1)!\cdot(n+1-i)!}

分析

由于差分之后常系数是 iki^k 那么可以推出他是 k+1k+1 次多项式，只需求 k+2k+2 个点就能唯一确定了。

part 1：普通 O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
using namespace std;
template<typename T>inline void read(T &x){
	x=0;T f=1;char ch=getchar();
	while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
	while(ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
template<typename T>inline void write(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
const int N=2e3+8;
const int mod=998244353;
int n,k;
int x[N],y[N];
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1; 
	}
	return res;
}
int main(){
    read(n),read(k);
    for(int i=1;i<=n;i++){
        read(x[i]),read(y[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int res=y[i];
        int res1=1,res2=1;
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            res1=(1ll*res1*(k-x[j]))%mod;
            res2=(1ll*res2*(x[i]-x[j]))%mod;
        }
        ans=(ans+1ll*res*res1%mod*qmi(res2,mod-2)%mod)%mod;
    }
    write((ans+mod)%mod);
    return 0;
}

part2：O(n) 值域连续。

__END__