题解 P4948 【数列求和】
Weng_Weijie
·
·
题解
题意：求\sum_{i=1}^ni^ka^i
要分两种情况考虑
(1) a \neq 1
令
S(k)=\sum_{i=1}^ni^ka^i
S(k)=\sum_{i=1}^ni^ka^i=\sum_{i=1}^n(i+1)^ka^{i+1}-(n+1)^ka^{k+1}+a
=\sum_{i=1}^n\sum_{j=0}^k\binom{k}{j}i^ja^{i+1}-(n+1)^ka^{k+1}+a
=\sum_{j=0}^k\binom{k}{j}\sum_{i=1}^ni^ja^{i+1}-(n+1)^ka^{k+1}+a
=a\sum_{j=0}^k\binom{k}{j}S(j)-(n+1)^ka^{k+1}+a
移项
S(k)=\dfrac{(n+1)^ka^{k+1}-a\displaystyle\sum_{j=0}^{k-1}\binom{k}{j}S(j)-a}{a-1}
***
(2)$a=1
S(k)=\sum_{i=1}^ni^k
S(k)=\sum_{i=1}^n(i+1)^k-(n+1)^k+1
=\sum_{i=1}^n\sum_{j=0}^k\binom{k}{j}i^j-(n+1)^k+1
=\sum_{j=0}^k\binom{k}{j}\sum_{i=1}^ni^j-(n+1)^k+1
=\sum_{j=0}^k\binom{k}{j}S(j)-(n+1)^k+1
\sum_{j=0}^{k-1}\binom{k}{j}S(j)-(n+1)^k+1=0
\binom{k}{k-1}S(k-1)=(n+1)^k-\sum_{j=0}^{k-2}\binom{k}{j}S(j)-1
S(k)=\dfrac{(n+1)^{k+1}-\displaystyle\sum_{j=0}^{k-1}\binom{k+1}{j}S(j)-1}{k+1}
```cpp
#include <iostream>
using LL = long long;
LL n;
const int mod = 1E9 + 7;
const int K = 2005;
int a, k, C[K][K], S[K];
void up(int &x, int y) { if ((x += y) >= mod) x -= mod; }
int pow(LL x, LL y) {
int ans = 1; x %= mod; y %= mod - 1;
for (; y; y >>= 1, x = static_cast<LL> (x) * x % mod)
if (y & 1) ans = static_cast<LL> (ans) * x % mod;
return ans;
}
int main() {
std::cin >> n >> a >> k;
C[0][0] = 1;
for (int i = 1; i < K; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
up(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
}
if (a == 0) std::puts("0");
if (a == 1) {
S[0] = n % mod;
for (int i = 1; i <= k; i++) {
int sum = 0;
for (int j = 0; j < i; j++) up(sum, static_cast<LL> (C[i + 1][j]) * S[j] % mod);
up(sum = mod - sum, pow(n + 1, i + 1) - 1);
S[i] = static_cast<LL> (sum) * pow(i + 1, mod - 2) % mod;
}
std::printf("%d\n", S[k]);
}
if (a > 1) {
S[0] = static_cast<LL> (pow(a, n + 1) - a + mod) * pow(a - 1, mod - 2) % mod;
for (int i = 1; i <= k; i++) {
int sum = 0;
for (int j = 0; j < i; j++) up(sum, static_cast<LL> (C[i][j]) * S[j] % mod);
up(sum = mod - sum, static_cast<LL> (pow(n + 1, i)) * pow(a, n) % mod - 1);
S[i] = static_cast<LL> (sum) * a % mod * pow(a - 1, mod - 2) % mod;
}
std::printf("%d\n", S[k]);
}
return 0;
}
```