kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2021 Round2A : Hard TwoPolarStations

この回、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)の漸化式に気付く部分だよな…。