jzoj5923

我們可以記f[i]表示i個點的連通圖的個數

則我們可以考慮將i個點不必聯通的圖個數（記為g）減去i個點的不連通圖個數

那麼f[i]=g[i]-c(j-1,i-1)f[j]gi-j

枚舉一個j，強制將j定為包含點1的聯通塊的點的個數

然後這兩個部分不能連邊

則現在的不連通圖個數為（使j個點聯通的方案(i-j)個點不必聯通的方案在2i這些點中，選出j-1個點作為i聯通塊內部的點的方案個數）並且我們這i個點不能全聯通，所以j只能枚舉到i-1 再記f1[i]表示i個點最大聯通塊點數<=k的方案數枚舉一個j表示現在包含1的聯通塊大小那麼j對答案的貢獻為(使j個點聯通的方案*(i-j)個點中最大聯通塊點數<=k的方案數*在2i這些點中，選出j-1個點作為i聯通塊內部的點的方案個數）

由於我們最大聯通塊個數不能超過k，所以j不能超過min(i,k)

那麼f1[i]=c(j-1,i-1)*f[j]*f1i-j

也是這兩部分不能連邊

最後，我們答案說最大聯通塊大小==k，所以可以拆成<=k和<k的情況，相減就是答案

這種dp方式比較套路，但是比較難想到，所以要多積累，多做這種類型的題

雖然可以使用ntt優化，但是暴力也足夠了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mo 998244353ll
ll n,k,f[2010],g[2010],jc[2010],ijc[2010],f1[2010];
ll qp(ll x,ll y){
	ll r=1;
	while(y){
		if(y&1)r=r*x%mo;
		x=x*x%mo;
		y>>=1;
	}
	return r;
}
ll c(ll x,ll y){
	return jc[y]*ijc[y-x]%mo*ijc[x]%mo;
}
ll getc(){
	jc[0]=ijc[0]=1;
	for(ll i=1;i<=n;i++){
		jc[i]=jc[i-1]*i%mo;
		ijc[i]=qp(jc[i],mo-2);
	}
	g[1]=1;
	for(ll i=2;i<=n;i++)
		g[i]=qp(2,i*(i-1)/2);
	f[1]=1;
	for(ll i=2;i<=n;i++){
		f[i]=g[i];
		for(ll j=1;j<i;j++)
			f[i]=(f[i]-f[j]*g[i-j]%mo*c(j-1,i-1)%mo+mo)%mo;
	}
}
ll solve(ll k){
	memset(f1,0,sizeof(f1));
	f1[1]=f1[0]=1;
	for(ll i=2;i<=n;i++)
		for(ll j=1;j<=min(i,k);j++)
			f1[i]=(f1[i]+f[j]*f1[i-j]%mo*c(j-1,i-1)%mo)%mo;
	return f1[n];
}
int main(){
	freopen("bomb.in","r",stdin);
	freopen("bomb.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	getc();
	printf("%lld\n",(solve(k)-solve(k-1)+mo)%mo);
}

巴特西

jzoj5923

最新文章

热门文章