AOJ 2397 : Three-way Branch

問題リンク：Three-way Branch | Aizu Online Judge

問題概要；
H*Wのセルからなるグリッドが存在する
自分は最初セル(1,1)にいて、セル(W,H)に移動する
今いるセルの左下、下、右下に移動できる
いくつかのセル上には障害物が存在しており、そのセルに移動することはできない
セル(W,H)に移動する経路は何通り存在するか？
答えは1000000009でmodをとること
障害物は最大３０個存在する

解法：
状態の遷移を行列に落とし繰り返し二乗法を使い計算する

例えば以下の用なグリッドを考える
左上が(1,1)で右下が(W,H)である
'.' はなにもないセルを表し、
'x' は障害物があるセルを表す
b1,b2,b3,b4,b5はそのセルへの経路の総和をもつ行列

.. b1 = [1 0]
.. b2 = [1 1]
.. b3 = [2 2]
.x b4 = [4 0]
.. b5 = [4 4] よって答えは4

まず、1行目から3行目までを考える
1行目から3行目までは以下の行列を使う

A = [1 1] //(1,y)から下、右下に移動できる
    [1 1] //(2,y)から下、右下に移動できる

b2' = A * b1' ('は転置行列)
b3' = A * b2' = A * A * b1'

3行目から4行目のを考える
ここには障害物が存在するため、以下の様な行列を使う

A2 = [1 1] //(1,y)から下、右下に移動できる
     [0 0] //(2,y)からはどこにも移動できない

b4' = A2 * b3' = A2 * A * A * b1'

最後に、4行目から5行目に移動することを考える
これは最初と同様で障害物がないので行列Aを使う

b5' = A * b4' = A * A2 * A * A * b1'

以上の様にして計算する
障害物をy座標毎にまとめておき、
スタート地点から最初の障害物があるy軸までの A のn乗と障害物に対応させた
特別な行列A2を計算し、それを最後まで繰り返す

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define MOD 1000000009

using namespace std;
typedef long long ll;
typedef pair<ll,ll> Coor;

typedef vector<ll> VI;
typedef vector<VI> VVI;
typedef VVI matrix;

//行列

ll W,H,N;
int dx[] = {-1,0,+1};
map<ll,vector<int> > obstruction;

matrix getMatrix(vector<int> vec)
{
  bool out[W];
  rep(i,W)out[i] = false;
  rep(i,vec.size())out[vec[i]] = true;
  matrix A = identity(W);
  rep(i,W)A[i][i] = 0;
  rep(x,W)
    {
      if(out[x])continue;
      rep(k,3)
	{
	  int nx = x + dx[k];
	  if(!(0 <= nx && nx < W))continue;
	  A[x][nx] = 1;
	}
    }
  return A;
}

int main()
{
  int CNT = 1;
  while(scanf("%lld %lld %lld",&W,&H,&N),W|H|N)
    {
      obstruction.clear();
      vector<Coor> vec(N);
      vector<ll> b(W,0);
      b[0] = 1;
      bool out = false;
      rep(i,N)
	{
	  scanf("%lld %lld",&vec[i].first,&vec[i].second);
	  vec[i].first--,vec[i].second--;
	  if(vec[i].first == W-1 && vec[i].second == H-1)out = true;
	  if(vec[i].second == 0)continue;
	  if(vec[i].second == H-1)continue;
	  obstruction[vec[i].second].push_back(vec[i].first);
	}

      if(out)
	{
	  cout << "Case " << CNT++ << ": " << 0 << endl;
	  continue;
	}

      matrix A = getMatrix(vector<int>());
      matrix ans = identity(W);

      ll cur = 0;
      for(map<ll,vector<int> >::iterator it = obstruction.begin();it!=obstruction.end();it++)
	{
	  vector<int> obst = it->second;
	  matrix B = getMatrix(obst);
	  ll diff = (it->first) - cur - 1;

	  if(diff != 0)
	    {
	      matrix tmp = pow(A,diff);
	      ans = multi(tmp,ans);
	    }

	  ans = multi(B,ans);
	  cur = (it->first);

	}

      if((H-1) != cur)
	{
	  matrix tmp = pow(A,(H-1)-cur);
	  ans = multi(tmp,ans);
	}

      VI vans = multi(ans,b);
   
      cout << "Case " << CNT++ << ": " << vans[W-1]%MOD << endl;

    }
  return 0;
}