ARC115-D Odd Degree

D - Odd Degree

まず次数が奇数の頂点数はかならず偶数個なのはサンプルから察する

*1 上の話なので基底を作るみたいなことが出来ないかなと考える
実際出来て、
　という二つの辺を使う使わないで出来る4つのパターンは
　による4つのパターンと同じことがすぐ分かる

同様に
　は　　に変えられる
（　　は偶奇を一切変えない辺のことで、偶奇を変えないので無視して最後に答えを2倍すれば良い）

これによって入力は（の辺を除き）互いに素なスターグラフの和集合になる
葉が個のスターグラフから辺をいくつか選んで次数奇数の頂点をちょうど個作る方法は、辺を本選ぶ時と本選ぶ時の合計通りである
（前者は選ばれた辺の葉とスターの中心が奇数次数の頂点になり、後者は葉のみが奇数次数の頂点になる）

あとはDPなどを使って全てのスターグラフについて足し合わせると良い

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using namespace atcoder;
using mint=modint998244353;

typedef pair<int,int> P;
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()

mint dp[6000];//答え

mint Factorial[50000],Finverse[50000];
void Cinit(){
  Factorial[0]=1;
  for(int i=1;i<50001;i++)Factorial[i]=Factorial[i-1]*i;
  Finverse[49999]=Factorial[49999].inv();
  for(int i=49998;i>=0;i--)Finverse[i]=(i+1)*Finverse[i+1];
}
mint nCk(int n,int k){
  if(n<k)return 0;
  return Factorial[n]*Finverse[k]*Finverse[n-k];
}

bool count(P e,int v){//辺eの端点に頂点vがあるか
  return e.first==v||e.second==v;
}
void change(P &a,P b){//辺aに対して辺bを用いて基底変換の操作
  if(a==b)a=P(0,0);
  else if(a==P(b.second,b.first))a=P(0,0);
  else if(a.first==b.first)a.first=b.second;
  else if(a.second==b.first)a.second=b.second;
  else if(a.first==b.second)a.first=b.first;
  else if(a.second==b.second)a.second=b.first;
}

int main(){
  Cinit();

  int n,m;cin>>n>>m;
  vector<P> v(m);
  REP(i,m)cin>>v[i].first>>v[i].second;

  int basesize=0;//スターグラフに関わる辺の個数
  set<int> center;//スターグラフの中心の集合

  for(int i=1;i<=n;i++){
    bool leaf=false;//頂点iがスターグラフの葉になるかどうか
    for(int j=basesize;j<m;j++)leaf|=count(v[j],i);//まだ葉に選ばれてない辺にiが存在するならiは葉になる
    if(!leaf)center.insert(i);//存在しない場合はスターグラフの中心になる
    else{//葉になる場合
      int idx;//頂点iを葉にする辺のindex
      REP(j,m)if(count(v[j],i))idx=j;
      REP(j,m)if(j!=idx&&count(v[j],i))change(v[j],v[idx]);//他の辺にはiが入らない様にする
      swap(v[basesize],v[idx]);basesize++;//vの最初のbasesize個が葉の辺になるようにする
    }
  }
  //この時点でvは最初のbasesize個がスターグラフの辺、残りは(0,0)になってる

  dp[0]=1;
  int mx=0;//dpの値が正である最大のindex　無駄な遷移を防ぐ
  for(int p:center){
    int k=0;//中心がpのスターグラフの大きさ
    REP(i,basesize)k+=count(v[i],p);

    for(int i=mx;i>=0;i-=2)
      for(int j=2;j<=k+1;j+=2)
        dp[i+j]+=dp[i]*(nCk(k,j-1)+nCk(k,j));

    mx+=(k+1)&(~1);
  }

  mint A=mint(2).pow(m-basesize);//スターグラフに入らなかった辺の個数分2をかける
  for(int i=0;i<=n;i++)cout<<(dp[i]*A).val()<<endl;
}

atcoder.jp

*1:mod 2の世界的なやつ