题目传送门：P4593 [TJOI2018] 教科书般的亵渎

前置知识：求自然数幂和

定义 $S_k(n)=\sum\limits_{i=1}^n i^k =1^k+2^k+\cdots +n^k$，则可以用伯努利数或者拉格朗日插值法求出公式。此处我们用一种更初等的递推方法，只需要知道二项式定理即可，其复杂度为 $O(k^2)$。

注意到 $S_k(n)$ 总是一个关于 $n$ 的 $k+1$ 次多项式，我们想找到 $S_k(n)$ 和 $S_{k-1}(n)$ 之间的关系，可以利用二项式定理构造一个递推公式。

二项式定理：$(x+y)^n=\sum\limits_{j=0}^{n} \binom{n}{j}x^{n-j}y^{j}$。

考虑：

$$(i+1)^{k+1}-i^{k+1}=\sum\limits_{j=0}^{k} \binom{k+1}{j}i^j$$

对 $i$ 将 $1 \sim n$ 求和：

$$\begin{aligned} \sum_{i=1}^n \left[ (i+1)^{k+1}-i^{k+1} \right]=&\sum\limits_{j=0}^{k}\binom{k+1}{j}\sum\limits_{i=1}^{n}i^j\\ \\ (n+1)^{k+1} - 1 =& \sum_{j=0}^k \binom{k+1}{j} S_j(n)\\ \\ (n+1)^{k+1} - 1 =&\binom{k+1}{k}S_k(n)+\sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n)\\ \\ S_k(n)=&\dfrac{(n+1)^{k+1}-1-\sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n)}{\binom{k+1}{k}}\\ \\ =&\dfrac{(n+1)^{k+1}-1-\sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n)}{k+1}\\ \end{aligned}$$

从而我们得到了求 $S_k(n)$ 的方法，时间复杂度为 $O(k^2)$（在预处理组合数的情况下）。

做题过程

（此处默认 $a$ 数组升序排序）

最初的局面分为 $m+1$ 块（可以是空的），分别是 $1\sim a_1-1,a_1+1\sim a_2-1,\dots ,a_m+1\sim n$。

打出第一张“亵渎”时可以让第一个怪物死亡，从而触发第二次“亵渎”——第二个怪物的血量降为 $1$ 点了。以此类推，知道打出“亵渎”前血量为 $a_1-1$ 的怪物死亡后又触发了一轮，此时原先血量为 $a_1+1$ 的怪物血量降为 $1$，但是由于没有原血量为 $a_1$ 的怪物，因而没有怪物死亡，所以需要再打出一张“亵渎”。

所以得出结论：每个块需要一张“亵渎”来消灭，更严谨地，每少一种血量的怪物，就要多用一张“亵渎”。所以可以轻松得出 $k=m+1$。

我们对于一个一般化的场面模拟一下运行过程：

$1\sim a_1-1$	$a_1+1\sim a_2-1$	$a_2+1\sim a_3-1$	$\dots$	$a_m+1\sim n$
$——$	$1\sim a_2-a_1-1$	$a_2-a_1+1\sim a_3-a_1+1$	$\dots$	$a_m-a_1-1\sim n-a_1$
	$——$	$1\sim a_3-a_2-1$		$a_m-a_2+1\sim n-a_2$
$——$				$1\sim n-a_m$

将每行统计一下和得到：

$S_k(n)-\sum\limits_{i=1}^{m} {a_i}^k$
$S_k(n-a_1)-\sum\limits_{i=2}^{m} {(a_i-a_1)}^k$
$S_k(n-a_2)-\sum\limits_{i=3}^{m} {(a_i-a_1)}^k$
$\dots$
$S_k(n-a_m)$

设 $a_0=0$，则上所有式相加得 $\sum\limits_{i=0}^{m}[S_k(n-a_i)-\sum\limits_{j=i+1}^{m}(a_j-a_i)^k]$。这就是我们要求的最终答案了。

且别忘了一个特判：如果连续至 $n$ 的一段怪物都没有，一定要将 $n$ 和 $m$ 减去相应的数量。

代码实现

需掌握知识：快速幂、质模数乘法逆元、杨辉三角求组合数。

首先预处理出 $1 \sim k+1$ 的组合数和逆元：

for(int i=0;i<=52;i++){//杨辉三角求组合数
    for(int j=0;j<=i;j++){
        if(!j||j==i)c[i][j]=1;
        else c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
    }
}
for(int i=1;i<=52;i++)//费马小定理求逆元
    ny[i]=power(i,p-2);

然后写出 $S_k(n)$ 的递推公式。

void solve(long long n,int m){
    s[0]=n%p;//边界
    for(int k=1;k<=m;k++){
        s[k]=power(n+1,k+1)-1;
        for(int i=0;i<k;i++){
            s[k]=(s[k]-c[k+1][i]*s[i]%p+p)%p;//及时取模
        }
        (s[k]*=ny[k+1])%=p;//乘 k+1 的逆元
    }
}

• 此函数的传参 $m$ 代表用到的最大 $k$。

然后就是主函数了，按照之前推的式子一步步来。先将 $a$ 数组排序，然后循环求答案：

sort(a+1,a+1+m);
long long ans=0;
for(int i=0;i<=m;i++){
    solve(n-a[i],m+1);
    (ans+=s[m+1])%=p;
    for(int j=i+1;j<=m;j++){
        ans=(ans-power(a[j]-a[i],m+1)+p)%p;
    }
}

记得处理特殊情况：

while(a[m]==n){
    n=a[m]-1;
    m--;
}

最终代码

#include<iostream>
#include<algorithm>
using namespace std;
const long long p=1e9+7;
long long power(long long a,int k){
    a%=p;
    long long s=1;
    while(k){
        if(k&1)s=s*a%p;
        a=a*a%p;
        k>>=1;
    }
    return s;
}
long long c[53][53],s[52],ny[53];
void m_c(){
    for(int i=0;i<=52;i++){
        for(int j=0;j<=i;j++){
            if(!j||j==i)c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
        }
    }
    for(int i=1;i<=52;i++)
        ny[i]=power(i,p-2);
}
void solve(long long n,int m){
    s[0]=n%p;
    for(int k=1;k<=m;k++){
        s[k]=power(n+1,k+1)-1;
        for(int i=0;i<k;i++)
            s[k]=(s[k]-c[k+1][i]*s[i]%p+p)%p;
        (s[k]*=ny[k+1])%=p;
    }
}
int T,m;
long long n,a[51];
int main(){
    m_c();
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=m;i++)cin>>a[i];
        sort(a+1,a+1+m);
        while(a[m]==n){
            n=a[m]-1;
            m--;
        }
        long long ans=0;
        for(int i=0;i<=m;i++){
            solve(n-a[i],m+1);
            (ans+=s[m+1])%=p;
            for(int j=i+1;j<=m;j++)
                ans=(ans-power(a[j]-a[i],m+1)+p)%p;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

时间复杂度 $O(Tk^3)$，AC 记录。