AtCoder ARC #115 : D - Odd Degree

よろしくない出来。
https://atcoder.jp/contests/arc115/tasks/arc115_d

問題

N頂点M辺の無向グラフが与えられる。
ここから各辺を残す・残さないの異なる2^M通りの部分グラフを考える。
次数が奇数である点がi個であるようなグラフは何通りか、各iについて答えよ。

解法

連結成分毎に見ていく。
もし連結成分が木だとすると、次数が奇数になる頂点が、任意の偶数個となるケースに対し、辺の残る・残らないがそれぞれ一意に定めることができる。
連結成分が木でない場合、全域木を使って次数の偶奇を合わせるとすると、残った辺はどうおいてもよいので、残った辺がp個あるなら、頂点の偶奇の組み合わせはそれぞれ2^p通りずつ作ることができる。

これを連結成分毎に行うことで、各連結成分毎に次数が奇数である頂点数ごとに辺の組み合わせを数え上げることができる。
最後に連結成分毎の結果をDPで合わせよう。

int N,M;
set<int> E[5050];
const ll mo=998244353;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<5050> uf;

int V[5050],NE[5050];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

vector<ll> add(vector<ll>& A,vector<ll>& B) {
	int x=A.size(),y=B.size(),z=x+y-1;
	vector<ll> C(z);
	int i,j;
	FOR(i,x) FOR(j,y) (C[i+j]+=A[i]*B[j])%=mo;
	return C;
	
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].insert(y);
		E[y].insert(x);
		uf(x,y);
	}
	
	FOR(i,N) V[uf[i]]++, NE[uf[i]]+=E[i].size();
	vector<ll> A={1};
	FOR(i,N) if(V[i]) {
		vector<ll> B(V[i]+1);
		FOR(j,V[i]+1) if(j%2==0) B[j]=comb(V[i],j)*modpow(2,NE[i]/2-(V[i]-1))%mo;
		A=add(A,B);
	}
	
	FOR(i,N+1) cout<<A[i]<<endl;
	
	
}

まとめ

木は思いついたもののDFS木の方向に走ってしまい失敗。