sum of powers

题意：

考虑所有的可重集{a1,a2,a3....ak} 满足a1+a2+....+ak=n,求所有a1^m+a2^m+a3^m的和

n,m,k<=5000

题解：

part1：

考虑f[i][j]表示前i个，总和为j

决策有两种1

1。之前的都加1

2。插入一个1

然后对于之前的都加一说是用斯特林数还原。。以后再学。。

part2：

满分做法。。挺简单的

考虑单独的贡献

枚举每个出现的次数，然后乘以组合数就可以了