kmjp's blog

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

みんなのプロコン 2019 決勝 : E - Espionage

一時期これ系の問題yukicoderで連発したよね。
https://atcoder.jp/contests/yahoo-procon2019-final-open/tasks/yahoo_procon2019_final_e

問題

N個のビルがあり、それぞれM階建である。
以下のように移動する際、経路が何通りか答えよ。

  • 1番のビルの1階から始め、そこに戻ってくる。その過程で、最後に1番のビルの1階に戻るタイミング以外で同じビルの同じ階を2回以上通ることはできない。
  • 上記の条件のもと、現在地から以下のいずれかの位置に移動できる。
    • 同じビルの上下の隣接階
    • 任意のビルの同じ階

解法

Mが大きいので行列累乗は推測が付きやすい。
1階~(K-1)階までの経路が確定し、(K-1)階とK階を行き来するビルの数が決まっているとき、K階と(K+1)階を行き来するビルの数とその際の組み合わせが何通りになるかを考えてみる。

(K-1)階とK階を行き来するビルの数が2n個あるとする。n箇所はK階から(K-1)階に下り、別のn箇所は(K-1)階からK階に上るとする。
すなわち、(K-1)階以下でn個のパスがあることになる。
この時の組み合わせをf(K,n)としよう。ここからf(K+1,m)という状態に至るケースが何通りか考え、その組み合わせ数を行列A(m,n)に設定しよう。

まずDPでf(2,n)を求めると、上記行列A^(M-2)を掛け合わせてf(M,m)を求めることができる。
あとはM階でm個のパスを連結するようにすれば解が求められる。

残るはA(m,n)の求め方である。解説ではO(N^3)で求められるとあるが、ここでは考え方が容易なO(N^4)解法を紹介。
n個のパスのうち、K階においてx個が連結することで減少し、また別に新たにy個のパスが生成されるとする。
すなわちm=n-x-yである。n,x,yを総当たりし、それぞれにおける組み合わせをA(n,m)に足しこんでいこう。

n,x,yが定まったとき、K階におけるビル間の移動の組み合わせは以下のように求められる。

  • n個のパスのうちx個が他と連結して消滅するとして、C(n,x)個消滅対象を選ぶ。
  • そのx個がどこに連結するかは、(n-x)*(n-x+1)*...*(n-1)通りとなる。
  • 新規にy個のパスが生成されるので、始点と終点を求めよう。これはC(N-2n,y)*P(N-2n-y,y)通りである。
  • 残された(N-2n*2y)個の頂点を、既存のパスに追加しよう。
int N,M;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

const int MAT=101;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};
ll mo=1000000007;

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

ll comb(ll N_, ll C_) {
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll fdp[101],tdp[101];
Mat A;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	comb(1,1);
	
	cin>>N>>M;
	for(i=1;i<=N/2;i++) {
		fdp[i]=comb(N,i)*comb(N-i,i)%mo*fact[i]%mo;
		FOR(j,N-2*i) fdp[i]=fdp[i]*(i+j)%mo;
	}
	
	for(i=1;i<=N/2;i++) { // cur
		for(j=0;j<i;j++) { //del
			ll pat=comb(i,j);
			FOR(x,j) pat=pat*(i-j+x)%mo;
			for(x=0;2*x+2*i<=N;x++) { //add
				ll pat2=pat*comb(N-2*i,x)%mo*comb(N-2*i-x,x)%mo*fact[x]%mo;
				int cand=x+2*i-j;
				FOR(y,N-2*i-2*x) {
					pat2=pat2*cand%mo;
					cand++;
				}
				(A.v[i][i-j+x] += pat2)%=mo;
			}
		}
	}
	auto B=powmat(M-2,A);
	FOR(x,N) FOR(y,N) (tdp[y]+=B.v[x][y]*fdp[x])%=mo;
	ll ret=0;
	FOR(x,N) if(tdp[x]) {
		ll pat=fact[x-1]*tdp[x]%mo;
		int cand=x;
		FOR(y,N-2*x) {
			pat=pat*cand%mo;
			cand++;
		}
		ret+=pat;
	}
	cout<<ret%mo<<endl;
}

まとめ

2次元版はyukicoderとかでも見たしね。