本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15689484.html

题目链接

由于BZOJ已挂，这里是黑暗爆炸和hydro的备份

黑暗爆炸：

hydro：

题目

Katharon 国有着悠久的历史，每个慕名而来的游客都渴望能在 Katharon 国发现一些奇怪的宝藏。而作为国王的 Kanari 君也梦想着有一天发现自己国家的宝藏,从而成为世界上最富有的人。 Kanari 国王和 katherine 皇后凭着 14 年真挚的感情，数十年如一日甜蜜地生活在一起。前几天恰逢劳动节放假， Kanari 国王便和 Katherine 皇后一同前往电影院观看了最新出版的电影《致青春》。看完之后两人对青春又有了更深刻的认识。然而在返程的路上，他们突然在路边的小树林里发现了一块奇怪的石板，上面印着一行小字：“如果你能破解下面表达式的结果，你就可以拥有 Katharon 国最珍贵的财产。”这时 Kanari 国王和 Katherine 皇后再也顾不上秀恩爱了，只好拿出草纸拼命计算这个表达式的结果。可是两人能力有限，现在，他们找到擅长数学的你，想请你来帮助他们完成这个愿望，如果你能回答正确，他们愿意把 Katharon 国最珍贵的财产分给你一半哦。这个表达式就是：

∑i=1nim×mi\sum_{i=1}^n i^m \times m^i
i=1∑n​im×mi

思路

题目就是求：

∑i=1nimmi\Large\sum_{i=1}^ni^mm^i

由于 mm 很小，nn 很大，所以考虑dp。

设 dpidp_i 表示：

dpi=∑j=1njimj\Large dp_i=\sum_{j=1}^nj^im^j

假设我们要求 (m−1)dpi(m-1)dp_i。

则：

(m−1)dpi=m×dpi−dpi\Large (m-1)dp_i=m\times dp_i-dp_i

带入 dpdp 的定义：

m×∑j=1njimj−∑j=1njimj\Large m\times \sum_{j=1}^nj^im^j-\sum_{j=1}^nj^im^j

把前面的 mm 弄进去：

∑j=1njimj+1−∑j=1njimj\Large \sum_{j=1}^nj^im^{j+1}-\sum_{j=1}^nj^im^j

把 mj+1m^{j+1} 变成 mjm^j：

∑j=2n+1(j−1)imj−∑j=1njimj\Large \sum_{j=2}^{n+1}(j-1)^im^j-\sum_{j=1}^nj^im^j

把 ∑j=2n+1\sum_{j=2}^{n+1} 变成 ∑j=1n\sum_{j=1}^n，也就是我们要减去一项 j=1j=1 再加上一项 j=n+1j=n+1

∑j=1n(j−1)imj+(n+1−1)mmn+1−(1−1)mm1−∑j=1njimj\Large \sum_{j=1}^n(j-1)^im^j+(n+1-1)^mm^{n+1}-(1-1)^mm^1-\sum_{j=1}^nj^im^j

化简：

∑j=1n(j−1)imj+nmmn+1−0im1−∑j=1njmmj\Large \sum_{j=1}^n(j-1)^im^j+n^mm^{n+1}-0^im^1-\sum_{j=1}^nj^mm^j

nmmn+1+∑j=1n(j−1)imj−∑j=1njimj\Large n^mm^{n+1}+\sum_{j=1}^n(j-1)^im^j-\sum_{j=1}^nj^im^j

后面的合并：

nmmn+1+∑j=1nmj((j−1)i−ji)\Large n^mm^{n+1}+\sum_{j=1}^nm^j((j-1)^i-j^i)

其中 (j−1)m(j-1)^m 可以用二项式定理化简。

nmmn+1+∑j=1nmj(∑k=0iCikjk(−1)i−k−ji)\Large n^mm^{n+1}+\sum_{j=1}^nm^j(\sum_{k=0}^iC_i^kj^k(-1)^{i-k}-j^i)

强行把 k=ik=i 的情况提出来：

nmmn+1+∑j=1nmj(∑k=0i−1Cikjk(−1)i−k+Ciiji(−1)i−i−ji)\Large n^mm^{n+1}+\sum_{j=1}^nm^j(\sum_{k=0}^{i-1}C_i^kj^k(-1)^{i-k}+C_i^ij^i(-1)^{i-i}-j^i)

化简：

nmmn+1+∑j=1nmj(∑k=0i−1Cikjk(−1)i−k+ji−ji)\Large n^mm^{n+1}+\sum_{j=1}^nm^j(\sum_{k=0}^{i-1}C_i^kj^k(-1)^{i-k}+j^i-j^i)

nmmn+1+∑j=1nmj(∑k=0i−1Cikjk(−1)i−k)\Large n^mm^{n+1}+\sum_{j=1}^nm^j(\sum_{k=0}^{i-1}C_i^kj^k(-1)^{i-k})

调整一下顺序：

nmmn+1+∑k=0i−1Cik(−1)i−k×∑j=1njkmj\Large n^mm^{n+1}+\sum_{k=0}^{i-1}C_i^k(-1)^{i-k}\times\sum_{j=1}^nj^km^j

明显，∑j=1nmjjk\sum_{j=1}^nm^jj^k 就是 dpdp 的定义，所以

nmmn+1+∑k=0i−1Cik(−1)i−k×dpk\Large n^mm^{n+1}+\sum_{k=0}^{i-1}C_i^k(-1)^{i-k}\times dp_k

而这个式子是 (m−1)dpi(m-1)dp_i，所以 dpidp_i 为：

dpi=nmmn+1+∑k=0i−1Cik(−1)i−k×dpkm−1\Large dp_i=\frac{n^mm^{n+1}+\sum_{k=0}^{i-1}C_i^k(-1)^{i-k}\times dp_k}{m-1}

O(m2)O(m^2) dp，初始化注意一下即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// Problem: L - 国王奇遇记
// Contest: Virtual Judge - 2021.12.12校内作业
// URL: https://vjudge.net/contest/472915#problem/L
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define mo 1000000007
#define N 1020
int n, m, i, j, k; 
int jc[N], f[N], p_1[N]; 

int kuai(int a, int b)
{
	int ans=1; 
	while(b)
	{
		if(b&1) ans=(ans*a)%mo; 
		b>>=1; 
		a=(a*a)%mo; 
	}
	return ans; 
}

int C(int m, int n)
{
	return jc[m]*kuai(jc[n]*jc[m-n]%mo, mo-2)%mo; 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	for(i=jc[0]=1; i<=1010; ++i) 
		jc[i]=jc[i-1]*i%mo; 
	for(i=0; i<=1010; ++i) p_1[i]=(i%2==1 ? -1 : 1); 
	n=read(); m=read(); 
	if(m==1) return printf("%lld", (1+n)*n/2%mo), 0; 
	f[0]=(kuai(m, n+1)-m)*kuai(m-1, mo-2)%mo; 
	for(i=1; i<=m; ++i)
	{
		f[i]=kuai(n, i)*kuai(m, n+1)%mo; 
		for(k=0; k<=i-1; ++k)
			f[i]=(f[i]+C(i, k)*f[k]%mo*p_1[i-k])%mo; 
		f[i]=f[i]*kuai(m-1, mo-2)%mo; 
	}
	printf("%lld", (f[m]%mo+mo)%mo); 
	return 0;
}