この回、MediumやHardは面白いのにEasyがひどすぎてもったいないよな。
https://community.topcoder.com/stat?c=problem_statement&pm=16984&rd=18683
問題
以下のような(N+2)点(2N+1)辺の無向グラフを考える。
まず、0～(N-1)番の点はサイクルを成すように順に並んでいる。
加えて、N番とN+1番の点の間には辺がある。
0～(N-1)番のうち、指定された区間L個分の点はN番との間に辺を持つ。
また、0～(N-1)番のうち、残りのR=(N-L)点は(N+1)番との間に辺を持つ。
このグラフの最小全域木は何通りあるか。
解法
Nが大きいので行列木定理は使えない。
まず以下の図形を定義する。
- n点のホイール：n個の頂点がサイクルとなし、それとは別に中心点があって中心点とn点の間に辺があるグラフ
- n点の扇形：n個の頂点がパスをなし、それとは別に中心点があって中心点とn点の間に辺があるグラフ。(パスの両端を連結するとホイールになる。
次に以下を考える。
W(n) := n点のホイールにおける最小全域木の数
F(n) := n点の扇型における最小全域木の数
T(n) := n点の扇型において、パスの両端が異なる連結成分になるよう、2つの連結成分になる最小全域木の数
詳細はEditorialに譲るが、以下の関係がある。
F(n) := 3*F(n-1)-F(n-2)
W(n) := F(n)+T(n) (n点の扇型において、パスの両端を連結する場合としない場合を考えるとよい。)
T(n) := 2*(F(1)+F(2)+....+F(n-1)) (中心点を含むk点の扇形と、残り(n-k)点のパスに分割するケースを考えるとよい)
これを踏まえて考える。
- N番と(N+1)番の辺を全域木に残す場合、実質残りの辺の選び方はn点のホイールからの全域木の選びかたと同じなのでW(n)通り
- N番と(N+1)番の辺を全域木に残さない場合、L＞0かつR＞0の場合を考える。2つの扇形が1つまたは2つの辺で連結した形状となる。
- 2つの扇形の両端をいずれも結ぶ場合、いずれかの扇形内は非連結でないといけないのでT(L)*F(R)+F(L)*R(L)
- 2つの扇形の両端を片方だけ結ぶ場合、2*F(L)*F(R)
const ll mo=1000000007; const int MAT=3; struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};}; Mat mulmat(Mat& a,Mat& b,int n=MAT) { ll mo2=4*mo*mo; int x,y,z; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) { r.v[x][y] += a.v[x][z]*b.v[z][y]; if(r.v[x][y]>mo2) r.v[x][y] -= mo2; } FOR(x,n) FOR(y,n) r.v[x][y]%=mo; return r; } Mat powmat(ll p,Mat a,int n=MAT) { int i,x,y; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(i,n) r.v[i][i]=1; while(p) { if(p%2) r=mulmat(r,a,n); a=mulmat(a,a,n); p>>=1; } return r; } class TwoPolarStations { public: int count(int N, int lo, int hi) { int L=hi-lo+1; int R=N-L; // top two is connect Mat A; A.v[0][0]=3; A.v[0][1]=mo-1; A.v[1][0]=1; A.v[2][0]=2; A.v[2][2]=1; Mat B=powmat(N-1,A); ll ret=(B.v[0][0]+B.v[2][0])%mo; if(R) { Mat B=powmat(L-1,A); Mat C=powmat(R-1,A); (ret+=2*B.v[0][0]*C.v[0][0])%=mo; (ret+=B.v[2][0]*C.v[0][0])%=mo; (ret+=B.v[0][0]*C.v[2][0])%=mo; } return ret; } }
まとめ
一番難しいの、F(n)の漸化式に気付く部分だよな…。
