嘟嘟嘟
题面挺迷的，拿第一个样例说一下：
放第一次亵渎，对答案产生了(sum_{i = 1} ^ {10} i ^ {m + 1} - 5 ^ {m + 1})的贡献，第二次亵渎产生了(sum_{i = 1} ^ {5} i ^ {m + 1})的贡献。
反正我们的主要目标就是求(f(n) = sum _ {i = 1} ^ {n} i ^ {m + 1})。
这东西好像叫做自然数幂和，求法很多，但我现在只会用拉格朗日差值去求。
但是我也不知道为啥，求(m + 2)个函数值不对，非得求(m + 3)个再去差值。
别忘了每次减去不存在的数的贡献。
差值我用的是(O(n))的求法，这里推荐一个讲的不错的博客：博客
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxm = 55;
const ll mod = 1e9 + 7;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
ll n;
int m;
ll a[maxm];
In ll quickpow(ll a, ll b)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}
ll y[maxm], inv[maxm];
In void init()
{
for(int i = 1; i <= m + 2; ++i) y[i] = (y[i - 1] + quickpow(i, m + 1)) % mod;
ll fac = 1;
for(int i = 1; i <= m + 2; ++i) fac = fac * i % mod;
inv[m + 2] = quickpow(fac, mod - 2);
for(int i = m + 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll pre[maxm], suf[maxm];
In ll lag(ll k)
{
int n = m + 2;
pre[0] = k; suf[n + 1] = 1;
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] * (k - i) % mod;
for(int i = n; i >= 0; --i) suf[i] = suf[i + 1] * (k - i) % mod;
ll ret = 0;
for(int i = 0; i <= n; ++i)
{
ll tp = (i - 1 >= 0 ? pre[i - 1] : 1) * suf[i + 1] % mod * inv[i] % mod * inv[n - i] % mod;
if((n - i) & 1) tp = -tp;
ret = (ret + y[i] * tp % mod + mod) % mod;
}
return ret;
}
int main()
{
int T = read();
while(T--)
{
n = read(); m = read();
init();
for(int i = 1; i <= m; ++i) a[i] = read();
sort(a + 1, a + m + 1);
ll ans = 0;
for(int i = 1; i <= m + 1; ++i)
{
ans = (ans + lag(n - a[i - 1])) % mod;
for(int j = i; j <= m; ++j) ans = (ans - quickpow(a[j] - a[i - 1], m + 1) + mod) % mod;
}
write(ans), enter;
}
return 0;
}