bzoj5093：[Lydsy1711月赛]图的价值

首先考虑到这是一张有标号的图，每一个点的地位是相等的，因此我们只需要求出一个点的价值和乘上\(n\)就好了

考虑一个点有多少种情况下度数为\(i\)

显然我们可以让除了这个点的剩下的\(n-1\)个点之间的边随便连，之后这个点从\(n-1\)个点里选择\(i\)个连边就好了，于是是\(\binom{n-1}{i}\times 2^{\frac{(n-1)(n-2)}{2}}\)种情况这个点度数为\(i\)

我们现在要做的就是这个柿子了

\[n2^{\frac{(n-1)(n-2)}{2}}\sum_{i=0}^{n-1}\binom{n-1}{i}i^k
\]

我们考虑一下展开\(i^k\)，自然是用第二类斯特林数了

于是不管前面的，我们要求的东西是

\[\sum_{i=0}^{n-1}\binom{n-1}{i}\sum_{j=1}^kS_2(k,j)\times \binom{i}{j}j!
\]

我们把\(j\)放到前面来枚举

\[\sum_{j=1}^kS_2(j,k)j!\sum_{i=0}^{n-1}\binom{n-1}{i}\binom{i}{j}
\]

考虑一下\(\sum_{i=0}^{n-1} \binom{n-1}{i}\binom{i}{j}\)的组合意义，就是先从\(n-1\)里选择了\(i\)个又从\(i\)个里选择了\(j\)个，总体上看是选择了\(j\)个，是\(\binom{n-1}{j}\)种情况，但是我们只需要保证第一次选择的\(i\)完全包含\(j\)，显然完全包含\(j\)的集合有\(2^{n-1-j}\)个

于是我们能把柿子写成这个样子

\[\sum_{j=1}^kS_2(k,j)\times \binom{n-1}{j}2^{n-1-j}\times j!
\]

现在的瓶颈在于求第二类斯特林数，我们记得斯特林数有一个容斥写法

\[S_2(i,j)=\frac{1}{j!}\sum_{k=0}(-1)^k\binom{j}{k}(j-k)^i
\]

我们拆开组合数之后发现这是一个卷积的形式，因此我们可以用\(NTT\)在\(O(nlogn)\)的时间内卷出一行斯特林数来

于是就解决了

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=8e5+5;

const int mod=998244353;

const int G[2]={3,332748118};

int rev[maxn],n,k,fac[maxn],inv[maxn];

int a[maxn],b[maxn],len,ifac[maxn];

inline int ksm(int a,int b) {

    int S=1;

    while(b) {if(b&1) S=1ll*S*a%mod;b>>=1;a=1ll*a*a%mod;}

    return S;

}

inline void NTT(int *f,int o) {

	for(re int i=0;i<len;i++) if(i<rev[i]) std::swap(f[i],f[rev[i]]);

	for(re int i=2;i<=len;i<<=1) {

		int ln=i>>1,og1=ksm(G[o],(mod-1)/i);

		for(re int l=0;l<len;l+=i) {

			int t,og=1;

			for(re int x=l;x<l+ln;++x) {

				t=1ll*og*f[x+ln]%mod;

				f[x+ln]=(f[x]-t+mod)%mod;

				f[x]=(f[x]+t)%mod;

				og=1ll*og*og1%mod;

			}

		}

	}

	if(!o) return;

	int inv=ksm(len,mod-2);

	for(re int i=0;i<len;i++) f[i]=1ll*f[i]*inv%mod;

}

int main() {

	n=read(),k=read();fac[0]=1,inv[1]=1;ifac[0]=1;

	for(re int i=2;i<=k;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	for(re int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod;

	for(re int i=1;i<=k;i++) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;

	len=1;while(len<=k+k+2) len<<=1;

	for(re int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?len>>1:0);

	for(re int i=0;i<=k;i++)

		a[i]=1ll*ifac[i]*ksm(i,k)%mod;

	for(re int i=0;i<=k;i++)

		if(i&1) b[i]=(mod-ifac[i])%mod;else b[i]=ifac[i];

	NTT(a,0),NTT(b,0);

	for(re int i=0;i<len;i++) a[i]=1ll*a[i]*b[i]%mod;

	NTT(a,1);

	int tot=n-1,now=1,ans=0;

	for(re int i=1;i<=k;i++) {

		now=1ll*now*tot%mod;

		tot--;if(tot<0) break;

		ans=(ans+1ll*a[i]*now%mod*ksm(2,n-1-i)%mod)%mod;

	}

	LL t=1ll*(n-1)*(n-2)/2;t%=(mod-1);

	ans=1ll*ans*n%mod;

	ans=1ll*ans*ksm(2,t)%mod;

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj5093：[Lydsy1711月赛]图的价值

最新文章

热门文章