読者です 読者をやめる 読者になる 読者になる

AOJ2397 Three-way Branch

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397

縦に長いグリッドが与えられる。(0, 0)の位置から(W-1, H-1)の位置に移動したい。移動の方法は、左下に、真下、右下のいずれかである。途中、N個の障害物が有り、その場所は移動できない。移動の方法は何通りあるか。mod\ 10^9+9で出力せよ。

  • 1\le W\le 75
  • 2\le H\le 10^{18}
  • 0\le N\le 30

解法

行について、i列目からi-1,\ i,\ i+1列目に遷移し、パターン数を加算することから、i\ (0\le i\le W-1)列目の1回の移動について、W\times Wの遷移行列を作ることができる。よって、障害物を考えなければY\ (1\le Y\le H)回移動するための遷移行列は、繰り返し二乗法を用いた行列累乗でO(W^3\times log(H))で求めることができる。障害物は高々30個しかないので、上から障害物のある場所までの遷移行列を計算し、障害物のマスのパターン数を0にクリアして、次の障害物の場所まで計算することを繰り返せば、全体でO(N\times W^3\times log(H))で解が求まる。また、MODの値は10^9+9であることに注意する。

typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll MOD = 1e9+9;

mat mul(mat const& A, mat const& B) {
  mat C(A.size(), vec(B[0].size()));
  for(int i=0; i<A.size(); i++)
    for(int k=0; k<B.size(); k++)
      for(int j=0; j<B[0].size(); j++)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  return C;
}

mat pow(mat A, ll n) {
  mat B(A.size(), vec(A.size()));
  for(int i=0; i<A.size(); i++) {
    B[i][i] = 1;
  }
  while(n > 0) {
    if(n & 1) B = mul(B, A);
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}

int W; ll H; int N;
mat coef;
vector<pair<ll, vector<int>>> vs;
mat xsmat;

void make_identity_coef() {
  coef.clear(); coef.resize(W); rep(i, W) coef[i].resize(W);
  rep(i, W) rep(j, 3)
    if(i+j-1 >= 0 && i+j-1<W)
      coef[i][i+j-1] = 1;
}

void init_xsmat() {
  xsmat.clear();
  xsmat.resize(W);
  rep(i, xsmat.size()) xsmat[i].resize(1);
  xsmat[0][0] = 1;
}

void input_blocks() {
  vs.clear();
  map<ll, vector<int>> y2xs;
  rep(i, N) {
    ll x, y; scanf("%lld%lld", &x, &y); x--, y--;
    y2xs[y].push_back(x);
  }
  for(auto& e: y2xs) vs.emplace_back(e.first, e.second);
  vs.emplace_back(H - 1, vector<int>());
}

void update_n_step(ll n) {
  xsmat = mul(pow(coef, n), xsmat);
}

int main() {

  for(int tc = 1; scanf("%d%lld%d", &W,&H,&N) && (W|H|N); tc++) {
    input_blocks();
    make_identity_coef();
    init_xsmat();
    ll curr = 0;
    rep(i, vs.size()) {
      update_n_step(vs[i].first - curr);
      curr = vs[i].first;
      for(auto& x: vs[i].second) xsmat[x][0] = 0;
    }
    printf("Case %d: %lld\n", tc, xsmat[W-1][0]);
  }

  return 0;
}