题解 P4593 【[TJOI2018]教科书般的亵渎】

· · 题解

题目意思有些乱

但其实实际上我们可以转化成求\sum_{i=1}^{n}{i^k}

那么这就是个经典的求自然数幂和的问题了，有很多种方法解决，以下给出几种常见方法

１．递推法

令其为S(n,k),可得

(i + 1)^{k + 1} - i^{k + 1} = \binom{k + 1}{1}i^k + \binom{k + 1}{2} i^{k - 1} + ... + \binom{k + 1}{k}i + 1

相加可得

(n + 1)^{k + 1} - 1 = \binom{k + 1}{1}\sum\limits_{i = 0}^{n}i^k + \binom{k + 1}{2}\sum\limits_{i = 0}^{n}i^{k-1} + ... + \binom{k + 1}{k}\sum\limits_{i = 0}^{n}i + n S(n,k)=\frac{1}{k+1}((n+1)^{k+1}-\sum_{i=2}^{k+1}\binom{k+1}{i}S(n,k+1-i)-1)

于是这样我们可以在O(k^2)的时间搞定

２．Bernoulli数

但是我们也可以用Bernoulli数来解决

可得到

S(n,k)=\frac{1}{k+1}\sum_{i=1}^{k+1}\binom{k+1}{i}B_{k+1-i}(n+1)^i

其中B_0=1,对于n>0有

\sum_{i=0}^{n}\binom{n+1}{i}B_i=0

３．Stirling数

(1)下降幂：x^{\underline{n}} = \frac{x!}{(x-n)!}

(2)第一类斯特林数:\left[\begin{matrix} n \\ k \end{matrix}\right] = (n - 1)\left[\begin{matrix} n - 1 \\ k \end{matrix}\right] + \left[\begin{matrix} n - 1 \\ k - 1 \end{matrix}\right]

那么我们可得

k! \binom{n}{k} = \sum_{i = 0}^{k} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i n^k = k! \binom{n}{k} - \sum_{i = 0}^{{k - 1}} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i

所以有\sum_{i = 0}^{n} i^k = \sum_{i = 0}^{n} \left( k! \binom{i}{k} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} i^j \right)

= k! \sum_{i = 0}^{n} \binom{i}{k} - \sum_{i = 0}^{n} \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} i^j 
                 $$= k! \binom{n + 1}{k + 1} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j}{\sum_{i = 0}^{n} i^j}$$
                 $$= \frac{(n + 1)^{\underline{k + 1}}}{k + 1} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j}{\sum_{i = 0}^{n}i^j}$$

4.多项式差分

考虑f(n)=n^k这一函数的差分表的第0条对角线 c_0...c_k.

我们有

\sum_{i = 0}^{n} f(i) = \sum_{i = 0}^{n} \sum_{j = 0}^{k} c_j \binom{i}{j} 
                  $$= \sum_{j = 0}^{k} \sum_{i = 0}^{n} c_j \binom{i}{j}$$
                  $$= \sum_{j = 0}^{k} c_j \binom{n + 1}{j + 1}$$

如果模数为质数,就可以O(k^2)计算了.

5.拉格朗日插值

从上面方法可看出\sum_{i=0}^{n}{i^k}是一个关于n的k+1次多项式，插一下值就好了

我们把n=0…k+1的函数值算出来

于是可以做到O(k)或O(klogk)求n_0时的函数值

我用的是Bernoulli数的方法

代码如下：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline long long read() {
 long long x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
const int mod=1e9+7;
long long n,a[65];
int m;
int b[65],c[65][65],inv[65];
long long qpow(long long x,long long y){
       long long res=1;
       while(y){
          if(y&1)res=res*x%mod;
          x=x*x%mod;
          y>>=1;
       }
       return res;
}
int fx(long long x){
     int res=0;
     F(i,1,m+1){
        res=(res+1ll*c[m+1][i]*b[m+1-i]%mod*qpow(x+1,i)%mod)%mod;
     }
     res=1ll*res*qpow(m+1,mod-2)%mod;
     return res;
}
int main () {
#ifndef ONLINE_JUDGE
file("4593");
#endif
    int t=read();
    F(i,1,60)inv[i]=qpow(i,mod-2);
    F(i,0,60){
        c[i][0]=1;
      F(j,1,i){
         c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
      }
    }
    b[0]=1;
    F(i,1,60){
       b[i]=0;
       F(j,0,i-1)b[i]=(b[i]+1ll*c[i+1][j]*b[j])%mod;
       b[i]=(1ll*(mod-b[i])*inv[i+1])%mod;
    }
    while(t--){
      n=read();
      m=read();
      F(i,1,m)a[i]=read();
      a[++m]=++n;
      sort(a+1,a+m+1);
      long long ans=0;
      F(i,1,m){
          F(j,i,m){
             ans=(ans+fx(a[j]-1)-fx(a[j-1])+mod)%mod;
          }
          F(j,i+1,m)a[j]-=a[i];
          a[i]=0;
      }
      printf("%lld\n",ans);
    }
    return 0;
}