题解 CF932E 【Team Work】

Great_Influence

2018-03-04 15:08:52

题解

数论推式子。

\sum\limits_{i=1}^nC(n,i)i^k =\sum\limits_{i=0}^nC(n,i)i^k =\sum\limits_{i=0}^n\frac{n!}{i!(n-i)!}\sum\limits_{j=0}^kS(k,j)C(i,j)j! =\sum\limits_{i=0}^n\frac{n!}{(n-i)!}\sum\limits_{j=0}^kS(k,j)\frac{1}{(i-j)!} =\sum\limits_{i=0}^n\sum\limits_{j=0}^kS(k,j)\frac{n!}{(n-i)!(i-j)!} =\sum\limits_{j=0}^kS(k,j)\sum\limits_{i=0}^n\frac{(n-j)!}{(n-i)!(i-j)!}*\frac{n!}{(n-j)!} =\sum\limits_{j=0}^kS(k,j)\frac{n!}{(n-j)!}\sum\limits_{i=0}^n C(n-j,n-i) =\sum\limits_{j=0}^kS(k,j)\frac{n!}{(n-j)!}2^{n-j}

(其中S(i,j)表示第二类斯特林数)

此时即可O(k^2)预处理第二类斯特林数，在O(k)计算即可。

注意第1步。当k=0时，根据后面的计算，0^0被算为1，需要在最后减去。

代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
template<typename T>inline void read(T &x)
{
    T f=1;x=0;char c;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+(c^48);
    x*=f;
}
using namespace std;
void file()
{
#ifndef ONLINE_JUDGE
    freopen("dt.in","r",stdin);
    freopen("dt.out","w",stdout);
#endif
}
static int n,k;
const int mod=1e9+7;
const int MAXN=5e3+7;
static int S[MAXN][MAXN];
inline void predone(int lim)
{
    S[0][0]=1;
    Rep(i,1,lim)Rep(j,1,i)
        S[i][j]=(S[i-1][j-1]+1ll*S[i-1][j]*j%mod)%mod;
}
static int ans;
inline int power(int a,int b)
{
    static int sum;
    for(sum=1;b;b>>=1,a=1ll*a*a%mod)if(b&1)
        sum=1ll*sum*a%mod;
    return sum;
}
int main()
{
    file();
    read(n);read(k);
    predone(k);
    static int lag=1,p2=power(2,n),inv2=power(2,mod-2);
    Rep(i,0,k)
    {
        ans=(ans+1ll*lag*S[k][i]%mod*p2%mod)%mod;
        lag=1ll*lag*(n-i)%mod;
        p2=1ll*p2*inv2%mod;
    }
    if(!k)--ans;
    printf("%d\n",ans);
    return 0;
}