BSOJ 5553 wangyurzee的树 prufer序列容斥

BSOJ我也不知道在哪.

容易想到容斥。

考虑不合法的方案想到强制某个点的度数为限制即可。

这样就变成了了总方案-一个不合法+两个不合法-3个......的模型了。

坑点当强制两个相同的点时方案数为0.

当序列长度>n-2的时候方案数为0.

注意一些边界条件啥的。这样的话利用爆搜就很好写了。

const ll MAXN=1000010;

ll n,len,m;

ll ans,fac[MAXN],inv[MAXN];

ll w[MAXN],du[MAXN],vis[MAXN];

inline ll C(ll a,ll b){return a<b?0:fac[a]*inv[b]%mod*inv[a-b]%mod;}

inline ll ksm(ll b,ll p)

{

	ll cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b%mod;

		b=b*b%mod;p=p>>1;

	}

	return cnt;

}

inline void dfs(ll x,ll sum,ll cnt,ll v)

{

	if(x==m+1)

	{

		v=v*ksm(n-sum,n-2-cnt)%mod;

		if(sum&1)ans=(ans-v)%mod;

		else ans=(ans+v)%mod;

		return;

	}

	dfs(x+1,sum,cnt,v);

	if(du[x]-1<=n-2-cnt&&!vis[w[x]])

	{

		vis[w[x]]=1;

		dfs(x+1,sum+1,cnt+du[x]-1,v*C(n-2-cnt,du[x]-1)%mod);

		vis[w[x]]=0;

	}

}

signed main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);fac[0]=1;

	rep(1,m,i)get(w[i]),get(du[i]);

	rep(1,n,i)fac[i]=fac[i-1]*i%mod;

	inv[n]=ksm(fac[n],mod-2);

	fep(n-1,0,i)inv[i]=inv[i+1]*(i+1)%mod;

	dfs(1,0,0,1);putl((ans+mod)%mod);

	return 0;

}

巴特西

BSOJ 5553 wangyurzee的树 prufer序列容斥

最新文章

热门文章

巴特西

BSOJ 5553 wangyurzee的树 prufer序列 容斥

最新文章

热门文章

BSOJ 5553 wangyurzee的树 prufer序列容斥