今回何なんだ…。
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を先にやって大ダメージを負った。