自动搬运

查看原文

来自洛谷，原作者为

	Weng_Weijie やー！今日もパンがうまい！

搬运于2025-08-24 22:05:33，当前版本为作者最后更新于2018-10-27 07:44:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意：求$$\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} $$

$O(k^2)$递推即可

---

(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} $$

$O(k^2)$递推即可

#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;
}