[BZOJ 3157][BZOJ 3516] 国王奇遇记

3157 3516 题目大意

求$\sum_{i = 1}^{n}{ {i ^ m} \cdot {m ^ i} }$,其中$n \leq 10^{9},m \leq 1000$


思路

$m = 1$时答案为$\frac{n \cdot (n + 1)}{2}$

否则令$S_k = \sum_{i = 1}^{n}{i ^ k \cdot m ^ i}$

$S_0 = \sum_{i = 1}^{n}{m ^ i} = \frac{m ^ {n + 1} - m}{m - 1}$

对于$S_k$有

$(m - 1) \cdot S_k = \sum_{i = 1}^{n}{i ^ k \cdot m^{i + 1} } - \sum_{i = 1}^{n}{i ^ k \cdot {m ^ i} }$

$= \sum_{i = 1}^{n + 1}{(i - 1) ^ k \cdot m ^ {i + 1} } - \sum_{i = 1}^{n}{i ^ k \cdot m ^ i}$

$= n ^ k \cdot m^{n + 1} + \sum_{i = 1}^{n}{\sum_{j = 0}^{k - 1}{(-1) ^ {k - j} \cdot C_{j}^{k} \cdot i ^ j \cdot m ^ i} }$

$= n ^ k \cdot m ^ {n + 1} + \sum_{j = 0}^{k - 1}{(-1)^{k - j} \cdot C_{j}^{k} \cdot S_j}$

通过逆元可快速求$S_m \ mod \ 10 ^ 9 + 7$


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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int MOD = 1e9 + 7;
#define M 1010
int S[M],n,m,C[M][M];
inline int qpow(int a,int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = 1LL * ans * a % MOD;
a = 1LL * a * a % MOD;
b >>= 1;
}
return ans;
}
inline void iC(){for(int i = 1;i <= m;i++){C[i][0] = C[i][i] = 1;for(int j = 1;j < i;j++) C[i][j] = (0LL + C[i - 1][j - 1] + C[i - 1][j]) % MOD;}}
int main()
{
scanf("%d %d",&n,&m);
if(m == 1){printf("%lld",1LL * n * (n + 1) / 2 % MOD);return 0;}
iC();int inv = qpow(m - 1,MOD - 2);
S[0] = (1LL * ((qpow(m,n + 1) - m + MOD) % MOD) * inv) % MOD;
for(int i = 1;i <= m;i++)
{
S[i] = (1LL * qpow(n,i) * qpow(m,n + 1)) % MOD;
for(int j = 0;j < i;j++)
{
S[i] = (0LL + S[i] + (((i - j) & 1) ? (-1LL) : (1LL)) * (1LL * C[i][j] * S[j] % MOD)) % MOD;
S[i] = (0LL + S[i] + MOD) % MOD;
}
S[i] = (1LL * S[i] * inv + MOD) % MOD;
}
printf("%d",S[m]);
return 0;
}