(CF932E)Team Work

原题链接

思路:

推式子

最重要的一步是使用第二类斯特林数将普通幂转化为下降幂, 即:

$$i^k = \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} i^{\underline{j}}$$

于是有:

$$\begin{aligned} & \sum_{i=1}^n {n \choose i} i^k\\ = & \sum_{i=1}^n {n \choose i} \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} i^{\underline{j}}\\ = & \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} \sum_{i=1}^n \frac{n^{\underline{i}}}{(i-j)!}\\ = & \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} n^{\underline{j}}\sum_{i=1}^n \frac{(n-j)^{\underline{i-j}}}{(i-j)!}\\ = & \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} n^{\underline{j}} \sum_{i=1}^n {n-j \choose i-j}\\ = & \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} n^{\underline{j}} \sum_{i=1}^{n-j} {n-j \choose i}\\ = & \sum_{j=1}^k \begin{Bmatrix} k\\ j \end{Bmatrix} n^{\underline{j}} 2^{n-j} \end{aligned}$$

第二类斯特林数可以直接递推得到, 其他项边递推边计算即可.

代码:

#include <cstdio>
using LL = long long;
const int Mn(5050);
const LL MP(1000000007);

LL stir[Mn];    //斯特林数
LL ksm(LL a, LL p) {    //快速幂
    LL ret(1), tmp(a%MP);
    while(p) {
        if(p&1) {
            ret = ret*tmp%MP;
        }
        tmp = tmp*tmp%MP;
        p >>= 1;
    }
    return ret;
}

int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i(1);i<=k;++i) {    //递推计算
        stir[i] = 1;
        for(int j(i-1);j;--j) {
            stir[j] = (j*stir[j]%MP + stir[j-1]) % MP;
        }
    }
    LL ans(0);
    LL p1 = n, p2 = ksm(2,n-1); //下降幂项与普通幂项
    LL i2 = ksm(2,MP-2);    //2的逆元
    for(int j(1);j<=k;++j) {
        ans = (ans + stir[j]*p1%MP*p2%MP) % MP;
        p1 = p1*(n-j)%MP;
        p2 = p2*i2%MP;
    }
    printf("%lld",ans);
    return 0;
}