题意

给定 n , m n,m n,m

计算 ∑ i = 1 n i m ∗ m i \sum_{i=1}^ni^m*m^i ∑i=1n​im∗mi

n ≤ 1 0 9 , m ≤ 5000 n\le10^9,m\le5000 n≤109,m≤5000

题解

很玄妙的题，看起来完全不会做，实际上也完全不会做

考虑递推！

n n n很大，因此递推只可以和 m m m有关

和 m m m有关系的有两个，一个是指数上的，一个是底数上的

那么有三种情况，递推其中一个，或者两个一起

根据题解，我们考虑递推指数上的

那么设计状态 f i = ∑ j = 0 n j i ∗ m j f_{i}=\sum_{j=0}^{n}j^i*m^j fi​=∑j=0n​ji∗mj

可以发现， f 0 f_0 f0​就是等比数列求和，可以直接求出来，那么第一项就有了

那么问题在于转移，考虑用类似等比数列求和的方法来求和

也就是两边同时乘 m m m，然后做差

m f i = ∑ j = 0 n j i ∗ m j + 1 mf_{i}=\sum_{j=0}^{n}j^i*m^{j+1} mfi​=∑j=0n​ji∗mj+1

( m − 1 ) f i = ∑ j = 0 n j i ∗ m j + 1 − ∑ j = 0 n j i ∗ m j (m-1)f_i=\sum_{j=0}^{n}j^i*m^{j+1}-\sum_{j=0}^{n}j^i*m^j (m−1)fi​=j=0∑n​ji∗mj+1−j=0∑n​ji∗mj

= m n + 1 n m + ∑ j = 1 n ( j − 1 ) i ∗ m j − ∑ j = 1 n j i ∗ m j =m^{n+1}n^m+\sum_{j=1}^{n}(j-1)^{i}*m^{j}-\sum_{j=1}^{n}j^i*m^j =mn+1nm+j=1∑n​(j−1)i∗mj−j=1∑n​ji∗mj

= m n + 1 n m + ∑ j = 1 n m j ( ( j − 1 ) i − j i ) =m^{n+1}n^m+\sum_{j=1}^{n}m^j((j-1)^i-j^i) =mn+1nm+j=1∑n​mj((j−1)i−ji)

= m n + 1 n m + ∑ j = 1 n m j ( ∑ k = 0 i − 1 j k C i k ( − 1 ) i − k ) =m^{n+1}n^m+\sum_{j=1}^{n}m^j(\sum_{k=0}^{i-1}j^kC_{i}^{k}(-1)^{i-k}) =mn+1nm+j=1∑n​mj(k=0∑i−1​jkCik​(−1)i−k)

套路地转化主体

= m n + 1 n m + ∑ k = 0 i − 1 C i k ( − 1 ) i − k ∑ j = 1 n m j j k =m^{n+1}n^m+\sum_{k=0}^{i-1}C_{i}^{k}(-1)^{i-k}\sum_{j=1}^{n}m^jj^k =mn+1nm+k=0∑i−1​Cik​(−1)i−kj=1∑n​mjjk

可以发现，后面这个东西，不就是 f f f的定义吗？

= m n + 1 n m + ∑ k = 0 i − 1 C i k ( − 1 ) i − k f j =m^{n+1}n^m+\sum_{k=0}^{i-1}C_{i}^{k}(-1)^{i-k}f_j =mn+1nm+k=0∑i−1​Cik​(−1)i−kfj​

然后就得到了一个玄妙的 O ( m 2 ) O(m^2) O(m2)的做法

以后这种题，不妨试试递推的方式，然后通过类似等比数列求和的套路，同乘 m m m，尽量和之前的状态扯上关系，来得到可以递推的效果

em…听说还有 O ( m ) O(m) O(m)的做法，以后再来填吧

#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>using namespace std;typedef long long LL;const int N=255;const int MOD=1e9+7;int add (int x,int y) {x=x+y;return x>=MOD?x-MOD:x;}int mul (int x,int y) {return (LL)x*y%MOD;}int dec (int x,int y) {x=x-y;return x<0?x+MOD:x;}int Pow (int x,int y){if (y==1) return x;int lalal=Pow(x,y>>1);lalal=mul(lalal,lalal);if (y&1) lalal=mul(lalal,x);return lalal;}int n,m;int C[N][N];int f[N];int main(){scanf("%d%d",&n,&m);if (m==1){printf("%d\n",((LL)n*(n+1)/2)%MOD);return 0;}C[0][0]=1;for (int u=1;u<=m;u++){C[u][0]=1;for (int i=1;i<=u;i++) C[u][i]=add(C[u-1][i-1],C[u-1][i]);}f[0]=mul(mul(m,dec(1,Pow(m,n))),Pow(dec(1,m),MOD-2));int lalal=Pow(m,n+1),inv=Pow(m-1,MOD-2);for (int u=1;u<=m;u++){lalal=mul(lalal,n);int cnt=0;for (int j=0;j<u;j++){int now=mul(C[u][j],f[j]);if ((u-j)&1) cnt=dec(cnt,now);else cnt=add(cnt,now);}f[u]=mul(inv,add(lalal,cnt));}printf("%d\n",f[m]);return 0;}