[atARC115D]Odd Degree

考虑对于一棵树$G$，这个问题的答案——

当$k$为奇数时答案显然为0，否则从$V$中任选$k$个点，以任意一点为根，从底往上不难发现子图数量唯一

换言之，当$k$为偶数时，每一个合法（恰有$k$个奇度数的点）子图恰好对应于一种选择方案，即${|V|\choose k}$

当$G$是一张连通图时，继续来分析答案——

首先$k$仍要是偶数，且仍然考虑任选$k$点，并求出其一棵生成树

对于生成树以外的边，任意选每一条边是否加入子图，之后同样可以通过这棵生成树构造出一组方案，换言之每一组选点方案恰对应于$2^{|E|-|V|+1}$个子图，答案即${|V|\choose k}2^{|E|-|V|+1}$

有多个连通块时，显然每一个连通块独立，用$f_{i,j}$表示前$i$个连通块中选$j$个点，枚举最后一个所选的点转移即可，复杂度为$o(n^{2})$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5005

 4 #define mod 998244353

 5 int n,m,x,y,mi[N],fac[N],inv[N],f[N],szV[N],szE[N],dp[N][N];

 6 int c(int n,int m){

 7     return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;

 8 }

 9 int find(int k){

10     if (k==f[k])return k;

11     return f[k]=find(f[k]);

12 }

13 void merge(int x,int y){

14     x=find(x),y=find(y);

15     if (x==y)szE[x]++;

16     else{

17         f[x]=y;

18         szV[y]+=szV[x];

19         szE[y]+=szE[x]+1;

20     }

21 }

22 int main(){

23     mi[0]=fac[0]=inv[0]=inv[1]=1;

24     for(int i=1;i<N;i++)mi[i]=2*mi[i-1]%mod;

25     for(int i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%mod;

26     for(int i=2;i<N;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

27     for(int i=1;i<N;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;

28     scanf("%d%d",&n,&m);

29     for(int i=1;i<=n;i++){

30         f[i]=i;

31         szV[i]=1,szE[i]=0;

32     }

33     for(int i=1;i<=m;i++){

34         scanf("%d%d",&x,&y);

35         merge(x,y);

36     }

37     dp[0][0]=1;

38     int scc=0;

39     for(int i=1;i<=n;i++)

40         if (f[i]==i){

41             scc++;

42             for(int j=0;j<=n;j++)

43                 for(int k=0;k<=min(j,szV[i]);k+=2)

44                     dp[scc][j]=(dp[scc][j]+1LL*mi[szE[i]-szV[i]+1]*c(szV[i],k)%mod*dp[scc-1][j-k])%mod;

45         }

46     for(int i=0;i<=n;i++)printf("%d\n",dp[scc][i]);

47 }

巴特西

[atARC115D]Odd Degree

最新文章

热门文章