[TJOI2018]教科书般的亵渎

嘟嘟嘟




题面挺迷的，拿第一个样例说一下：

放第一次亵渎，对答案产生了\(\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;

}