Editorial見て解いちゃったけど、本番出てたら自力で解けたかなぁ…？
http://community.topcoder.com/stat?c=problem_statement&pm=14022
問題
N頂点からなる自己ループや多重辺のない無向グラフがオイラー的であるとは、以下の条件を満たす場合を示す。
- N頂点が連結である。
- ある点から始まり、全部の辺を１回ずつ通って元の位置に戻れる（頂点の通過回数は問わない）
ここで、N頂点からなる無向グラフが「ほぼオイラー的」とは、最大１辺まで、辺を追加または削除(多重辺や自己ループは不可)することでオイラー的になるものをいう。
Nに対し、N頂点からなるほぼオイラー的グラフの数を求めよ。
解法
オイラー的グラフは全頂点の次数が偶数であり、ほぼオイラー的グラフは次数が奇数の頂点が０個か２個である。
よってオイラー的グラフがあったとき、任意の２頂点を結ぶ辺を１本追加(まだその２点間に辺がない場合)または削除(すでにその２点間に辺がある場合)するとほぼオイラー的なグラフを作成できる。
また異なる２つのオイラー的グラフに１本辺を増減しても、同じほぼオイラー的グラフは生成されない。
よってE(n)をN頂点からなるほぼオイラー的グラフの数とすると、が求める解である。
あとはE(n)さえ求めればよい。
連結であるなしを問わず、各頂点の次数が偶数であるn頂点グラフの数をD(n)とする。
E(n) = D(n) - (非連結で各頂点の次数が偶数のn頂点グラフ)となる。両項目をそれぞれ求めていこう。
D(n)は次のように求められる。
まず1～nの頂点があるとして、n以外の頂点(n-1)個の間に自由に辺を張る。
すると1～(n-1)の間に次数が奇数の点がいくつか生じるので、それらの頂点をn番と辺を張る。
実際は(n番の頂点と辺を張る前は)次数が奇数の点は偶数個なので、最終的に各頂点の次数は偶数となる。
よって結局D(n)は、最初の(n-1)頂点間の辺の張り方の組み合わせ数と一致するので。
(非連結で各頂点の次数が偶数のn頂点グラフ)の分は包除原理の要領で処理できる。
n頂点のグラフのうち、1番の頂点を含む連結成分はx個(1≦x≦(n-1))だとする。
そのケースは、1番以外の(n-1)個の頂点から(x-1)個を選ぶ組み合わせと、残された(n-x)個が(連結か非連結かを問わず)次数が偶数の頂点を成すグラフを構成する組み合わせの積なので、通りである。
xを総当たりすると結局となる。
あとは上記DPをO(N^2)でやればよい。
ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } const int N_=2020; ll C_[N_][N_]; ll E[2020]; ll D[2020]; class AlmostEulerianGraph { public: int calculateGraphs(int n) { int i,j,k; FOR(i,N_) C_[i][0]=C_[i][i]=1; for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo; E[0]=D[0]=1; for(i=1;i<=2000;i++) { E[i]=D[i]=modpow(2,(i-1)*(i-2)/2); for(k=1;k<=i-1;k++) E[i]-=C_[i-1][k-1]*E[k]%mo*D[i-k]%mo; E[i]=(mo+E[i]%mo)%mo; } return E[n]*(1+n*(n-1)/2)%mo; } }
まとめ
最初は次数が奇数の頂点がある場合とない場合のグラフを連結していく方針を考えていたので、本番だと時間切れでダメだったかもな。
