[题解] Topcoder 15279 SRM 761 Div 1 Level 3 SpanningSubgraphs DP，容斥

题目

考虑DP。\(f(msk,i)\) 表示集合 \(msk(一定包含0号点)\) ，选了恰好i条边的连通方案数。转移用容斥，用这个点集内部所有连边方案减去不连通的。令\(|e_{msk}|\)表示两个端点都在集合msk内的边数，D为\(e_{\complement_{msk}sub}\)(sub在msk中补集内部的边集)。转移式：\(f(msk,i)=\binom{|e_{msk}|}{i}-\sum_{sub \in msk,0 \in sub,0 \leq j \leq i} f(sub,j)\cdot \binom{|D|}{i-j}\)，其中sigma是枚举不连通情况中0号点所在的连通块。直接转移是\(O(3^nm^2)\)的，考虑优化。

我们枚举msk，现在需要计算\(f(msk,*)\)的值。观察转移式，后面一部分是\(\sum_{sub \in msk,0 \in sub,0 \leq j \leq i} f(sub,j)\cdot \binom{|D|}{i-j}\)，枚举到\(f(sub,j)\)的时候，集合sub中的j条边已经确定要选了，我们现在要做的事就是依次决定sub外的\(|D|\)条边中哪些要选，如果有k条边选，就转移到\(f(msk,j+k)\)。

所以可以令\(g(i,j)\)表示已经有i条边确定要选，还有j条边“排队等待”决定。枚举所有可能转移到\(f(msk,*)\)的\(f(sub,j)\)，让\(g(j,|D|)+=f(sub,j)\)。然后对\(g\)数组再做一次DP：

\[g(i-1,j+1)+=g(i,j),g(i-1,j)+=g[i][j]
\]

两个转移分别代表一条待定边选或不选。注意转移g的时候j要从大到小枚举。最后我们让\(f(msk,i)-=g[i][0]\)就行了。总复杂度\(O(3^nm+2^nm^2)\)，常数很小可以通过。

注意自环的处理。

点击查看代码

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)

#define repn(i,n) for(int i=1;i<=n;++i)

#define LL long long

#define pii pair <LL,LL>

#define fi first

#define se second

#define mpr make_pair

#define pb push_back

using namespace std;

const LL MOD=1000000007LL;

LL qpow(LL x,LL a)

{

	LL res=x,ret=1;

	while(a>0)

	{

		if((a&1)==1) ret=ret*res%MOD;

		a>>=1;

		res=res*res%MOD;

	}

	return ret;

}

LL n,m,in[33000],f[17000][210],g[210][210],fac[210],inv[210],cc[20];

vector <LL> gg[20];

LL C(LL nn,LL mm){return fac[nn]*inv[mm]%MOD*inv[nn-mm]%MOD;}

struct SpanningSubgraphs

{

  vector <int> count(int N,vector <int> A,vector <int> B)

  {

    fac[0]=1;repn(i,205) fac[i]=fac[i-1]*(LL)i%MOD;

    rep(i,203) inv[i]=qpow(fac[i],MOD-2);

    n=N;m=A.size();

    rep(i,m) if(A[i]!=B[i])

    {

      gg[A[i]].pb(B[i]);

      gg[B[i]].pb(A[i]);

    }

    LL cnt=0;

    rep(i,m) if(A[i]==B[i])

    {

      ++in[1<<A[i]];++cc[A[i]];

      if(A[i]==0) ++cnt;

    }

    repn(i,(1<<n)-1)

    {

      int lowbit=(i&-i),id=__builtin_ctz(lowbit);

      in[i]=in[i^(1<<id)]+cc[id];

      rep(j,gg[id].size()) if((i&(1<<gg[id][j]))>0) ++in[i];

    }

    rep(i,cnt+1) f[0][i]=C(cnt,i);

    repn(msk,(1<<(n-1))-1)

    {

      int lim=in[(msk<<1)|1];

      rep(i,lim+2) rep(j,lim+2) g[i][j]=0;

      for(int sub=msk;;sub=(sub-1)&msk)

      {

        if(sub!=msk)

        {

          rep(i,in[(sub<<1)|1]+1)

            (g[i][in[(msk^sub)<<1]]+=f[sub][i])%=MOD;

        }

        if(sub==0) break;

      }

      rep(i,lim+1) for(int j=lim;j>0;--j) if(g[i][j]>0)

      {

        (g[i+1][j-1]+=g[i][j])%=MOD;

        (g[i][j-1]+=g[i][j])%=MOD;

      }

      repn(j,lim) f[msk][j]=(C(lim,j)-g[j][0]+MOD)%MOD;

    }

    vector <int> ans;

    for(int i=n-1;i<=m;++i) ans.pb(f[(1<<(n-1))-1][i]);

    return ans;

  }

};

巴特西

[题解] Topcoder 15279 SRM 761 Div 1 Level 3 SpanningSubgraphs DP，容斥

最新文章

热门文章