[TJOI2018] 教科书般的亵渎

前言

亵渎不是都退了好久了吗，哦，是2018年的题啊，那没事了

没DK我玩什么ss

题目

洛谷

讲解

其实这道题就是让你求(sum_{i=1}^n i^k)

我们令(S(n,k)=sum_{i=1}^n i^k)

我们来康康这个式子：

[(n+1)^k-n^k=sum_{i=1}^k C_k^i*n^{k-i} ]

然后我们可以列出共(n)个这样类似的式子：

[n^k-(n-1)^k=sum_{i=1}^k C_k^i*(n-1)^{k-i} ]

[(n-1)^k-(n-2)^k=sum_{i=1}^k C_k^i*(n-2)^{k-i} ]

...

[2^k-1^k=sum_{i=1}^k C_k^i*1^{k-i} ]

我们将这(n)个式子加起来康康会发生什么：

[(n+1)^k-1=sum_{i=1}^{k}C_k^i*S(n,k-i) ]

我们试图通过对式子变形来使得它出现(S(n,k))一项

[(n+1)^{k+1}-1=sum_{i=1}^{k+1}C_{k+1}^{i}*S(n,k-i+1) ]

[(n+1)^{k+1}-1=sum_{i=2}^{k+1}C_{k+1}^{i}*S(n,k-i+1)+C_{k+1}^1*S(n,k) ]

[(n+1)^{k+1}-1=sum_{i=2}^{k+1}C_{k+1}^{i}*S(n,k-i+1)+(k+1)*S(n,k) ]

出现目标！移项！

[S(n,k)=frac{(n+1)^{k+1}-1-sum_{i=2}^{k+1}C_{k+1}^{i}*S(n,k-i+1)}{k+1} ]

根据(C_n^m=C_n^{n-m})可推出：

[S(n,k)=frac{(n+1)^{k+1}-1-sum_{i=0}^{k-1}C_{k+1}^{i}*S(n,i)}{k+1} ]

(O(k^2))递推即可，其中边界为(S(n,0)=n)

然而我们发现求(sum_{i=1}^n i^k)的时候中间可能有断掉的几个数

但明显不会太多，暴力减掉即可

代码

void pre()
{
	C[0][0] = 1;
	for(int i = 1;i < MAXM;++ i)
	{
		C[i][0] = 1;
		for(int j = 1;j <= i;++ j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
	}
}
int qpow(LL x,int y)
{
	x %= MOD;
	int ret = 1;
	while(y){if(y & 1) ret = 1ll * ret * x % MOD;x = 1ll * x * x % MOD;y >>= 1;}
	return ret;
}
int S(int x)
{
	if(!x) return now;
	if(mem[x]) return mem[x];
	int ret = qpow(now+1,x+1) - 1;
	for(int i = 0;i < x;++ i) ret = (ret - 1ll * C[x+1][i] * S(i)) % MOD;
	ret = (ret + MOD) % MOD;
	ret = 1ll * ret * qpow(x+1,MOD-2) % MOD;
	return mem[x] = ret;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	pre();
	for(int T = Read(); T ;-- T)
	{
		n = Read(); m = Read();
		for(int i = 1;i <= m;++ i) a[i] = Read();
		sort(a+1,a+m+1);
		k = m+1; now = n;
		int ans = 0;
		for(int i = 1;i <= k;++ i)
		{
			for(int j = 0;j <= k;++ j) mem[j] = 0;
			ans = (ans + S(k)) % MOD;
			for(int j = i;j <= m;++ j) ans = (ans - qpow(a[j] - n + now,k) + MOD) % MOD;
			now -= a[i] - a[i-1];
		}
		Put(ans,'
');
	}
	return 0;
}