kmjp's blog

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

Codeforces #420 Div2 E. Okabe and El Psy Kongroo

今回何なんだ…。
http://codeforces.com/contest/821/problem/E

問題

2次元座標で格子点上(0,0)→(K,0)に移動することを考える。
座標上いくつかの線分(A[i],C[i])-(B[i],C[i])がある。
各線分はX座標が連続(B[i]=A[i+1])している。

以下の条件を満たす移動経路は何通りあるか。

  • (x,y)からは(x+1,y+1),(x+1,y),(x+1,y-1)のいずれかに移動できる。
    • ただしy<0には移動できない。
    • 線分より上に移動できない。すなわちA[i]≦x≦B[i]のときy≦C[i]でなければならない。

解法

C[i]は高々15なので、yの取りうる値は16通りである。
あとは行列累乗の要領で組み合わせを求めていこう。

線分の両端、すなわちB[i]=A[i+1]=xとなる座標では、y≦min(C[i],C[i+1])と2つの線分の影響を受ける点に注意。

int N;
ll K;
ll A[101],B[101],C[101];
ll V[16],V2[16];

const int MAT=16;
ll G[MAT][MAT],G2[MAT][MAT];
ll mo=1000000007;
void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=(x==y);
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) h[x][y]=0;
			FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	V[0]=1;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		for(y=C[i]+1;y<16;y++) V[y]=0;
		B[i]=min(K,B[i]);
		
		ZERO(G);
		FOR(x,16) {
			if(x-1>=0 && x-1<=C[i]) G[x-1][x]=1;
			if(x<=C[i]) G[x][x]=1;
			if(x+1<=C[i]) G[x+1][x]=1;
		}
		powmat(B[i]-A[i],16,G,G2);
		ZERO(V2);
		FOR(x,16) FOR(y,16) (V2[y]+=G2[y][x]*V[x])%=mo;
		swap(V,V2);
	}
	cout<<V[0]<<endl;
}

まとめ

Dを先にやって大ダメージを負った。