JZOJ 5923. 【NOIP2018模拟10.23】Bomb

题目

问n个点的图中，有多少张图的最大的连通块大小不超过k。

题解

计数。

从部分分里得到灵感，若k=n，则答案为n个点的连通图的张数。

容斥做不了？

我的想法是，全部的，去掉一个点不在连通块内的，加上两个点不在连通块内的……

这个方案是可行的，但是容斥系数配错了

该怎么容斥？显然，必须先选择计算i号点不在那个大连通块里面。

那么那个大连通块怎么表示？只能够强制1号点在里面。

剩余的n-1个点里面容斥。

但这样也不知道怎么做，只能请大佬去解答了。

做法1

考虑1号点连通块大小，则设f[i]为i个点的连通图的张数，g[i]表示i个点的图的个数。

显然， g [ i ] = 2 C ( i , 2 ) g[i]=2^{C(i,2)} g[i]=2C(i,2)

g [ i ] = Σ j = 1 i − 1 g [ i − j ] ∗ f [ j ] ∗ C ( i − 1 , j − 1 ) g[i]=Σ_{j=1}^{i-1} g[i-j]*f[j]*C(i-1,j-1) g[i]=Σj=1i−1​g[i−j]∗f[j]∗C(i−1,j−1)

多项式求逆。

然后做个背包就好了，设 h [ k ] [ i ] h[k][i] h[k][i]表示大小为i的图，其最大连通块大小不超过k。

反思

①计数题必须多做，熟练。

②老套路，pq个点，总共q个连通块，每块p个点的图的张数。

连通块无序，连通块中，点无序。

固定一个点不动。

式子： a [ p q ] = f [ p ] q ∗ B a[pq]=f[p]^q*B a[pq]=f[p]q∗B

B = ( p q ) ! q ! ∗ ( p ! ) q B=\frac{(pq)!}{q!*(p!)^{q}} B=q!∗(p!)q(pq)!​

递推式： a [ p q ] = a [ p ( q − 1 ) ] ∗ ( f [ p ] ∗ C p q − 1 p − 1 ) a[pq]=a[p(q-1)]*(f[p]*C_{pq-1}^{p-1}) a[pq]=a[p(q−1)]∗(f[p]∗Cpq−1p−1​)

定性地分析，就是新的集合里的第一个数只能够填数 p q − p + 1 , . . . , p q pq-p+1,...,pq pq−p+1,...,pq，在剩余的 p q − 1 pq-1 pq−1个数里选出 p − 1 p-1 p−1个数来成为最后一个集合的元素。

定量地分析，将式子写出来：

( p q ) ! ( p q − p ) ! q ! ∗ ( p ! ) q ( q − 1 ) ! ∗ ( p ! ) q − 1 = ( p q − p + 1 ) ∗ . . . ∗ ( p q − 1 ) ( p q − p ) ! ( p − 1 ) ! \frac{\frac{(pq)!}{(pq-p)!}}{\frac{q!*(p!)^q}{(q-1)!*(p!)^{q-1}}}=\frac{(pq-p+1)*...*(pq-1)}{(pq-p)!(p-1)!} (q−1)!∗(p!)q−1q!∗(p!)q​(pq−p)!(pq)!​​=(pq−p)!(p−1)!(pq−p+1)∗...∗(pq−1)​

③容斥：如果要求无序的，那么将最后一个点强制选，其他的随便选。

更优秀的做法

时间复杂度: O ( n 2 ) O(n^2) O(n2)

设 h [ k ] [ n ] h[k][n] h[k][n]表示n个点的图，有多少张的最大连通块大小 ≤ k \leq k ≤k。

答案为 h [ k ] [ n ] − h [ k − 1 ] [ n ] h[k][n]-h[k-1][n] h[k][n]−h[k−1][n]

h [ k ] [ n ] = ∑ i = 1 k f [ i ] ∗ C n − 1 i − 1 ∗ h [ n − i ] [ k ] h[k][n]=\sum_{i=1}^k f[i]*C_{n-1}^{i-1}*h[n-i][k] h[k][n]=i=1∑k​f[i]∗Cn−1i−1​∗h[n−i][k]

考虑1号点所在的连通块的大小。

小结

总而言之，需要考虑1号点的连通块大小。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 5010
#define mo 998244353
#define LL long long
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
int i,j,k,l,n,m;
LL f[N],g[N],h[N],w[N][N];
LL jc[N],ny[N]; 
LL C[N][N];
LL p2[N];
LL ksm(LL x,LL y){
	LL rs=1;
	for(;y;y>>=1,x=(x*x)%mo)if(y&1)rs=(rs*x)%mo;
	return rs;
}
int main(){
	scanf("%d%d",&n,&k);
	jc[0]=jc[1]=1;
	fo(i,2,n)jc[i]=(jc[i-1]*i)%mo;
	ny[0]=ny[1]=1;
	fo(i,2,n)ny[i]=ksm(jc[i],mo-2);
	C[0][0]=1;
	fo(i,1,n)fo(j,0,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	fo(i,0,n)p2[i]=ksm(2,C[i][2]);
	f[0]=1;f[1]=1;f[2]=1;
	fo(i,3,n){
		f[i]=p2[i];
		fo(j,1,i-1)
			f[i]=(f[i]-(f[j]*C[i-1][j-1]%mo)*p2[i-j]%mo+mo)%mo;
	}
	fo(i,1,k){
		w[i][0]=1;
		fo(j,1,n/i)w[i][j]=(w[i][j-1]*f[i]%mo*C[i*j-1][i-1])%mo;
	}
	g[0]=1;
	fo(i,1,k){
		fo(j,0,n)h[j]=0;
		fo(j,0,n)fo(l,1,j/i)
			h[j]=(h[j]+g[j-i*l]*w[i][l]%mo*C[j][l*i])%mo;
		fo(j,0,n)g[j]=(g[j]+h[j])%mo;
	}
	printf("%lld",h[n]);
	return 0;
}