AOJ2397 Three-way Branch

問題

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

縦に長いグリッドが与えられる。の位置からの位置に移動したい。移動の方法は、左下に、真下、右下のいずれかである。途中、個の障害物が有り、その場所は移動できない。移動の方法は何通りあるか。で出力せよ。

• 
• 
• 

解法

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

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