kmjp's blog

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

yukicoder : No.310 2文字しりとり

yukicoder

★４～５位の手抜き解法です。
http://yukicoder.me/problems/874

問題

N種類の文字がある言語がある。
２文字の単語はN*N通り考えられるが、うちM個辞書に載っていない単語がある。

辞書に載っている(N*N-M)個の単語をすべて１回ずつ使うしりとりをしたい。
単語順は何通り考えられるか。

解法

頂点を文字、単語を２つの文字をつなぐ有向辺としよう(同じ文字を２つ使う場合、ループも存在する)。
この問題は、全ての辺を１回ずつ辿るオイラー路の組み合わせ数を求める問題となる。

各頂点の入次数・出次数がすべて等しい(かつ全辺が連結)なら、このオイラー路はオイラー閉路となる。
また、入次数・出次数のどちらかが１多い頂点が１つずつあれば、このオイラー路の始点終点は確定する。

オイラー閉路の組み合わせ数の計算方法はすでに手法があるため、後者もオイラー閉路として扱いたい。
そこで、与えられたグラフが後者なら、（入次数の方が１多い点）から（出次数の方が１多い点）に１本辺を追加し、全点入次数と出次数が等しくなるようにしよう。
最初の１手はその追加した辺に固定したオイラー閉路を考えることは、辺を追加する前のグラフでオイラー路を考える事に等しくなる。

あとはこのオイラー閉路の組み合わせ数を求める問題に還元できる。
Editorialにもあるとおり、オイラー閉路の組み合わせ数はWikipediaに書いてある。
BEST theorem - Wikipedia

式は同じだが、上記定理の説明は以下のサイト(PDF)の方がわかりやすかった。
http://www.theoremoftheday.org/CombinatorialTheory/BEST/TotDBEST.pdf

さて、このこのBEST Theoremの計算過程では全域木の数を求める必要があり、それにはラプラシアン行列から１行１列削った行列の行列式が必要になる。
愚直に掃出し法を行うとこれはO(N^3)かかりTLEする。

そこでEditorialでは"black box linear algebra"という手法を紹介している(自分はまともに見てないし理解もしていない)。
ただ、このラプラシアン行列は対角成分以外はほとんど-1である。
よって掃出し法を行う際、適当に行を入れ替えると計算過程で多くの成分が0になり、大幅に高速化できる。
以下のコードでは、掃出し法の過程で乱択で行を入れ替えたところ、何とか通った。

なお、このBEST theoremで求められるのはオイラー閉路の数だけである。
実際にはこの問題のケースでは「どの辺から始まるか」を考慮する必要があるので、入次数・出次数がすべて等しい場合は辺の数である(N*N-M)倍する必要がある。
入次数・出次数のどちらかが１多い頂点が１つずつあるケースは最初の辺を固定しているので、(N*N-M)倍は必要ない。

int N,M;
int A[4040],B[4040];
int in[4040],out[4040];
int st,en;
ll fact[8080];

ll mo=1000000007;
int id[4040],rid[4040];
int edge[4040][4040];
ll mat[4040][4040];

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;
}

ll det_mo(int N) {
	int x,y,z;
	ll ret=1;
	FOR(y,N) FOR(z,N) mat[y][z]=((mat[y][z]%mo)+mo)%mo;
	FOR(x,N) {
		vector<int> V;
		for(y=x;y<N;y++) if(mat[y][x]) V.push_back(y);
		if(V.size()==0) return 0;
		y=V[rand()%V.size()];
		
		if(y!=x) {
			FOR(z,N) swap(mat[x][z],mat[y][z]);
			ret=(mo-ret)%mo;
		}
		ret=ret*mat[x][x]%mo;
		ll rev=modpow(mat[x][x]);
		FOR(z,N) mat[x][z]=rev*mat[x][z]%mo;
		for(y=x+1;y<N;y++) if(mat[y][x]) {
			rev=mat[y][x];
			for(z=x;z<N;z++) if(mat[x][z]) mat[y][z]=(mat[y][z]+mo*mo-mat[x][z]*rev)%mo;
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	srand(time(NULL));
	fact[0]=1;
	FOR(i,8000) fact[i+1]=fact[i]*(i+1)%mo;
	
	cin>>N>>M;
	FOR(i,N) {
		FOR(j,N) edge[i][j]=-1;
		in[i]=out[i]=N;
		edge[i][i]=N-1;
	}
	
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		
		out[x]--;
		in[y]--;
		edge[x][y]++;
		edge[y][y]--;
	}
	
	x=0;
	st=en=-1;
	FOR(i,N) {
		if(in[i]==0 && out[i]==0) id[i]=-1;
		else id[i]=x, rid[x]=i, x++;
		
		if(abs(in[i]-out[i])>1) return _P("0\n");
		if(in[i]==out[i]+1) {
			if(en!=-1) return _P("0\n");
			en=i;
		}
		if(out[i]==in[i]+1){
			if(st!=-1) return _P("0\n");
			st=i;
		}
	}
	if(x==0 || x==1) return _P("1\n");
	
	ll pat=(N*N-M)%mo;
	N=x;
	if(st>=0) { // odd
		in[st]++;
		out[en]++;
		edge[en][st]--;
		edge[st][st]++;
		pat=1;
	}
	
	FOR(i,N) pat = pat*fact[in[rid[i]]-1]%mo;
	FOR(i,N) FOR(j,N) mat[i][j]=edge[rid[i]][rid[j]];
	cout<<(pat*det_mo(N-1)%mo)<<endl;
	
}

まとめ

ひどい手抜き解答ではありますが…なんとか新年発yukicoderの前に全完に戻せました。