bzoj5093: [Lydsy1711月赛]图的价值

不难想到考虑每个点的贡献，ans=n*sigema(1~n)i C(n-1,i)*(2^C(n-1,2))*i^k

直接套第二类斯特林拆柿子即可。提示:sigema(1~n)i C(n,i)*C(i,j) = C(n,j)*2^(n-j)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxK=2e5+_;

const int fbiK=(<<)+_;

const int mod=;

inline int ad(int x,int y){return (x>=mod-y)?(x-mod+y):x+y;}

inline int re(int x,int y){return (x<y)?(x-y+mod):x-y;}

inline int mu(int x,int y){return (LL)x*y%mod;}

inline int qp(int x,int y){int r=;while(y>){if(y&)r=mu(r,x);x=mu(x,x);y/=;}return r;}

int fac[maxK],fac_inv[maxK],inv[maxK];

void yu(int K)

{

    fac[]=;for(int i=;i<=K;i++)fac[i]=mu(fac[i-],i);

    fac_inv[K]=qp(fac[K],mod-);

    for(int i=K-;i>=;i--)fac_inv[i]=mu(fac_inv[i+],i+);

    inv[]=;for(int i=;i<=K;i++)inv[i]=mu(inv[mod%i],mod-mod/i);

}

namespace GETS2

{

    int Re[*fbiK];

    void NTT(int *a,int n,int op)

    {

        for(int i=;i<n;i++)

            if(i<Re[i])swap(a[i],a[Re[i]]);

        for(int i=;i<n;i<<=)

        {

            int gn=qp(,(mod-)/(i<<));

            if(op==-)gn=qp(gn,mod-);

            for(int j=;j<n;j+=(i<<))

            {

                int g=;

                for(int k=;k<i;k++,g=mu(g,gn))

                {

                    int k1=a[j+k],k2=mu(a[j+k+i],g);

                    a[j+k]=ad(k1,k2);

                    a[j+k+i]=re(k1,k2);

                }

            }

        }

        if(op==-)

        {

            int inv=qp(n,mod-);

            for(int i=;i<n;i++)a[i]=mu(a[i],inv);

        }

    }

    int n,m,L,A[*fbiK],B[*fbiK],S2K[*fbiK];

    void main(int K)

    {

        m=*K-;for(n=;n<=m;n<<=)L++;

        for(int i=;i<n;i++)Re[i]=(Re[i>>]>>)|((i&)<<(L-));

        for(int i=;i<=K;i++)

        {

            A[i]=mu((i&)?mod-:,fac_inv[i]);

            B[i]=mu(qp(i,K),fac_inv[i]);

        }

        NTT(A,n,),NTT(B,n,);

        for(int i=;i<n;i++)S2K[i]=mu(A[i],B[i]);

        NTT(S2K,n,-);

    }

}

int S2[][];

void QWQ()

{

    S2[][]=;

    for(int i=;i<=;i++)

        for(int j=;j<=i;j++)

            S2[i][j]=ad(S2[i-][j-],mu(S2[i-][j],j));

}

int main()

{

    int n,K;

    scanf("%d%d",&n,&K);yu(K);

    GETS2::main(K);//QWQ();

    using namespace GETS2;

    int ans=,C=;

    for(int j=;j<=K;j++)

    {

        C=mu(mu(C,n-j),inv[j]);

        ans=ad(ans, mu( mu(S2K[j],fac[j]) , mu(C,qp(,n--j)) ) );

    }

    printf("%d\n", mu( mu(ans,n) , qp(,(LL)(n-)*(n-)/%(mod-)) ) );

    return ;

}