题解 P4948 【数列求和】

L2_sheep · 2018-11-03 18:31:36 · 题解

对于这题，介绍一种不用推公式的做法，其实就是错位相减法的递归运用，比较的直观。 错位相减法，大家应该比较了解，它可以很容易的推导出等比数列的求和公式。等比数列的系数都是常数项（0阶多项式），相邻两项的差都是0，很容易推出结果。 这题系数是k阶多项式。有个结论，将一个k阶多项式相邻的两项相减，会得到一个k-1阶多项式。这样经过k次相减后，最终将得到一个0阶多项式，这样就可以通过递归来得到结果。 举个例子： 具体代码如下：

#include <stdio.h>
#define N 2005
#define M 1000000007
typedef long long LL;

LL n, a, k, m, l;
LL dt[N], dw[N], inv, pa[N], pw;

LL ksm(LL x, LL y)
{
    if(y == 0) return 1;
    LL t = ksm(x, y >> 1);
    t = t * t % M;
    if(y & 1) t = t * x % M;
    return t;
}

LL jian(LL x, LL y){
    LL ans = x - y;
    if(ans < 0) ans += M;
    return ans;
}

LL cal(LL tk)
{
    LL ans = jian(pw * dw[1] % M, pa[k - tk + 1] * dt[1] % M);
    LL i;
    for(i = 1; i <= tk; i++){
        dt[i] = jian(dt[i + 1], dt[i]);
        dw[i] = jian(dw[i], dw[i + 1]);
    }
    if(tk > 0) return ans = jian(ans, cal(tk - 1)) * inv % M;
    return ans * inv % M;
}

int main() 
{
    LL i, j;

    scanf("%lld%lld%lld", &n, &a, &k);
    for(i = 1, j = n, m = k + 1, pa[0] = 1; i <= m; i++, j--){
        dt[i] = ksm(i, k);
        dw[i] = ksm(j % M, k);
        pa[i] = pa[i - 1] * a % M;
    }
    inv = ksm(a - 1, M - 2), pw = ksm(a, n + 1);
    printf("%lld\n", cal(k));  

    return 0;
}