CF932E Team Work

CodeForces

Luogu

分析

首先要知道

$$ m^n=\sum\limits_{i=0}^mC_m^i\cdot S(n,i)\cdot i $$

然后就可以大力推式子:

$$ \begin{aligned} &\quad\sum\limits_{i=1}^nC_n^i\cdot i^k\\ =&\sum\limits_{i=1}^nC_n^i\sum\limits_{j=0}^iC_i^j\cdot S(k,j)\cdot j!\\ =&\sum\limits_{i=1}^n\frac{n!}{i!(n-i)!}\sum\limits_{j=0}^i\frac{i!}{j!(i-j)!}\cdot S(k,j)\cdot j!\\ =&\sum\limits_{i=1}^n\frac{n!}{(n-i)!}\sum\limits_{j=0}^i\frac{S(k,j)}{(i-j)!}\\ =&\sum\limits_{j=0}^nS(k,j)\sum\limits_{i=j}^n\frac{n!}{(n-i)!}\cdot\frac{1}{(i-j)!}\\ =&\sum\limits_{j=0}^{\min(n,k)}S(k,j)\sum\limits_{i=j}^n\frac{n!}{(n-i)!}\cdot\frac{1}{(i-j)!}\\ =&\sum\limits_{j=0}^{\min(n,k)}S(k,j)\sum\limits_{i=0}^n\frac{n!}{(n-j)!}\cdot\frac{(n-j)!}{(n-i)!(i-j)!}\\ =&\sum\limits_{j=0}^{k}S(k,j)\frac{n!}{(n-j)!}\sum\limits_{i=0}^nC_{n-j}^{i-j}\\ =&\sum\limits_{j=0}^{k}S(k,j)\frac{n!}{(n-j)!}2^{n-j} \end{aligned} $$

$O(k^2)$预处理$S()$就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MOD=1e9+7;
const int MAXK=5000+10;

inline int FastPow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=1ll*a*a%MOD)
        if (b&1) ans=1ll*ans*a%MOD;
    return ans;
}

int S[MAXK][MAXK];

int main() {
    int n=read(),k=read();
    S[0][0]=1;
    for (re int i=1;i<=k;++i)
        for (re int j=1;j<=k;++j)
            S[i][j]=(S[i-1][j-1]+1ll*S[i-1][j]*j)%MOD;
    int ans=0;
    for (re int i=0,frac=1;i<=min(n,k);frac=1ll*frac*(n-i)%MOD,++i)
        ans=(ans+1ll*S[k][i]*frac%MOD*FastPow(2,n-i)%MOD)%MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 22 PM

发表评论