院試(東京大学大学院情報理工工学研究科 システム情報学 2016)
院試の受験記です。なんかの参考になれば。
準備編
試験は
- 英語(TOEFL ITP)
- 数学
- 専門
- 面接
があります。日程的に英語 -> (しばらく間が空く) -> 数学 -> 専門 -> 面接 でした(数学と専門は同じ日にやってほしい感)。
噂によると筆記試験(面接以外)でほぼ結果は決まっていて, その 3 科目の配点は 1:1:2 とからしいです。1:2:2 という噂もあります(ホントかは知りません)。
自分のやったお勉強について書きたいと思います。ここからめっちゃ Amazon ラッシュ。
ただ内部生の立場で書いているので外部にはあまり参考にならないかもしれません。
英語
まず TOEFL iBT を事前に受けるか 決められた日程に TOEFL ITP を受けるかを選択できますが, iBT は受験料がクッソ高い(たしか 2 万円とか)し難しいので, ITP のほうが良いと思います。
とりあえず問題内容を知っているのと知らないのでは 50 点くらい違いがあると思うので, それは予習しておきましょう。
- 作者: 島崎美登里,ポール・ワーデン,ロバート・ヒルキ
- 出版社/メーカー: 語研
- 発売日: 2010/03/16
- メディア: 単行本（ソフトカバー）
- 購入: 1人 クリック: 3回
- この商品を含むブログを見る
本番のリスニングはこれの 114514 倍速かったのでそこは別に対策した方が良いかもしれません。僕は全く聞き取れませんでした。
後文法は対策が非常に簡単で, 3 日くらい詰め込めば 8 割は余裕で取れるようになるのでそのために 1 冊買いました。
![全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])](https://images-fe.ssl-images-amazon.com/images/I/51bQaSjxNGL._SL160_.jpg "全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])")
全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])
- 作者: 林功
- 出版社/メーカー: 語研
- 発売日: 2012/05/29
- メディア: 単行本
- 購入: 9人 クリック: 13回
- この商品を含むブログ (1件) を見る
数学
線形代数と解析と確率が出るそうです。
数学に関しては公式ページに過去問があるのでそれをやっていれば良い点取れそうです。
線形代数は何も言わなくてもできそう。
解析は内部生なら数力演習のノート見直せば良さそうです(これで完璧に対策出来るとは言っていない)。
確率に関しては確率分布っぽい話と大学入試か？みたいのが混ざっています。内部生なら確率数理工学のノートを見返せば確率分布っぽいのが出たときの対策ができます。
専門
信号処理, 回路, 制御, コンピュータ, 力学 から 1 問ずつでて, その中から 3 問を解答します。これも公式ページに過去問があるのでそれで練習できます。ただ 2013 くらいからフォントがひどい(読めない)のがあるので文句言った方が良いと思います(僕は内部生なのでちゃんとした問題文を共有できたので問題なかったですが)。
信号処理は毎回狭く, 深く問うてくるイメージなので過去問解いても意味なさそうだし, 普通に難しいので僕は選択する気 0 でした。大学では信号処理論第一, 第二というのがあって, 第一の範囲はおおよそやる夫で勉強することができます。
www.ic.is.tohoku.ac.jp
今年の範囲は第二っぽかったです。第二の内容についてはよく知りません。
回路は毎年オペアンプが出ています。今年も毛色が若干変わったけど出ました。オペアンプを使った回路, 発振回路あたり勉強すれば良いのではないでしょうか。
制御は信号処理と違って毎年だいたい安定した問題が出ています。最近は古典制御の中にこっそり現代制御を仕込むみたいな形式が多かったですが, 今年は堂々と現代制御を出していました。下の 2 冊勉強すれば十分な気がします。
- 作者: 森泰親
- 出版社/メーカー: 森北出版
- 発売日: 2014/10/04
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
- 作者: 森泰親
- 出版社/メーカー: 森北出版
- 発売日: 2014/10/04
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (1件) を見る
コンピュータは…よくわからないので過去問だけやってました。今年はシミュレータでやれ💢💢というようなアセンブリを読まされる問題(再帰関数っぽかった)が出てよくわかりませんでしたが普段は結構簡単だと思います。暇だったらコンピュータの構成と設計でも読んでればよいのではないでしょうか。
- 作者: ジョン・L.ヘネシー,デイビッド・A.パターソン,成田光彰
- 出版社/メーカー: 日経BP社
- 発売日: 2014/12/06
- メディア: 単行本
- この商品を含むブログ (1件) を見る
力学はクッソ簡単な時があるのでそうだったら解こう, という感じで選択するつもりでした。1 年生の時に使ってた演習書が出てきたのでそれを使って一部勉強しました。
- 作者: 今井功,高見穎郎,高木隆司,吉沢徴,下村裕
- 出版社/メーカー: サイエンス社
- 発売日: 2006/09
- メディア: 単行本
- 購入: 1人 クリック: 21回
- この商品を含むブログ (3件) を見る
当日編
英語
リスニングで MP を使い果たす懸念をしていましたが全く聞き取れず MP を消費しなかったので他は計画通り解けました。
多分 リスニング 4 割, 文法 9 割, 長文 7 割くらいだと思います。
数学
「簡単すぎて差がつかない」と言っている人とそれを見て「ハーキレソー」と言ってる人がいました。
満点の自信は多少アリ。
専門
全然できなかったんですが周りも阿鼻叫喚だったので今年はそんな感じだったんだろうという感じでした。
5 割くらい？
追記
点数開示しました。300 円かかるのであんまりやりたくなかったんですが, 結局数学満点で自慢できたので良かったです(小並感)。
JAG 夏合宿に参加しました
楽しかったです。
前日
- 家で高速回転したり奇声を発したりしながら楽しみにしてました。
1 日目
- と言ってもシャイなのでビクビクしながら会場入りしました。
- 自己紹介でクソなぞなぞに言及したところ結構知られてるイメージでした。うれしい。
- ゆらふなさんと初めて会いました。これもうれしい。
- 懇親会。いろいろな人と話せて楽しかった。寿司はほとんど食べれなかった。egg fire。
2 日目
- 朝ごはんのブルーベリーゼリーが異様に濃い紫色でビビった(名物らしい)。
- コンテストは btk さん, たわしさんと組んだ。
- チーム全体で解いたのは C, D, H, I。
- C は btk さんが謎 TLE(入力がクソだった)を連発していて, 代わりに書いてみたら通った。
- D は問題読んで行けると思ったけど x/y の x, y が巨大になると勘違いした(実際には最初の歯車との比のみで決まるのでそんなことはない)のでたわしさんに実装を投げた。
- H, I はいつの間にか AC してた。
- 最後に F を通そうと思ったけど for 文のミスで死んだ。for 文は 1 行 に 1 個書くようにすれば防げるバグだったのですみませんという感じ。
- 解説聞いて L はなるほどという感じだった。
- 後で A は通したいぞい
3 日目
4 日目
- snuke さんのクソなぞなぞ日記が面白かった。そのあと悔しくて何個か駅を見て考えたけどあんまりおもしろいのは思いつかなかった。
- コンテストは btk さん, yurahuna さんと組んだ。in 六本木ヒルズ
- ACDFHJL を解きました。
- C は自明っぽい？(見てない) D は二分探索が嘘であることに気付いて O(N log^2 N) すれば OK
- L は知らんけど通してた
- A は後ろから見てけば良いんだけど O(N^3) しか思いつかなかったから yurahuna さんに投げたらいけそうな雰囲気にしてもらえたので投げた(そのあと大変そうだったけどなんとか通してた)
- F は各頂点で最短経路木を作ってほげる
- H は読めれば簡単
- J は dp[A] = (a の配列で合計を A にしたときの, b の配列側の最小値, およびそのとき選んだ集合) みたいのを更新していけば良い(btk さんと相談して出来た)
- I はほとんど 1/2 の確率で勝つとすると絶対に勝てる方法を btk さんが思いついたけど普通にアンチケースがあったっぽく死。後から聞いたら UMEKOMI すれば行けそうだった。
- コンテスト終わった後集まった人で築地に行って海鮮丼を食べた。いろいろ話せたし良かった。
— マヨ子@大天使クサハエル (@mayoko_) 2016年9月5日
夏合宿参加の皆さんがアップロードした美味しそうな画像たちを見ながら羽田で余った弁当を食べることに幸せを感じない
— Dで始まるくるくるくるりんが解けない人 (@Darsein) 2016年9月5日
まとめ
- egg fire
- くまみこは良かったぞ
AIM Tech Round 3 (Div. 1) C. Centroids
問題
頂点数 n の木 T 上の点 v が T の centorid であるとは, T から v を取り除いて得られる任意の連結成分が, 全て頂点数 n/2 以下であることを言う。
各頂点について, その頂点が以下の操作を一回以下許したとき centroid になるかどうかを判定せよ。
操作：木のある辺を消して, 好きな辺を加える(ただし新しいグラフも連結でなければならない)。
解法
操作を許さない場合にどうなるかを考えます。この場合はかなり単純です。頂点 v から伸びる辺の頂点から構成される部分木が, 全て n/2 以下の連結成分で構成されているか判定すれば良いです。いちいち頂点 v を根にして木dp しているとまにあわないですが, 0 を頂点にした木のみを考えて, 親方向側の連結成分の個数は n - (v の部分木のサイズ) というようにすれば良いです。
次に操作を許す場合を考えます。頂点 v の部分木でサイズが n/2 より大きいものがあった場合, その部分木の一部を切り取って v に直接つなぎかえるのが最適です。ここで部分木の頂点 ch で 2 通りの場合分けをします。
0 を根とした木でも ch が v の子である場合
この場合は, ch 以下の部分木を単純に調べるだけで良いので, euler_tour とか用意しておいてその中で部分木のサイズが n/2 である最大のものを求めます。ch の部分木のサイズ - この部分木のサイズ が n/2 以下なら操作をして centroid になることになります。
0 を根とした木で ch が v の親である場合
この場合がややこしいです。さらに二通りに分けます。
・つなげる木が v の祖先である場合
この場合, v からつなぎなおす頂点を a とすると, v - ch の木は,
- (a の部分木サイズ) - (v の部分木サイズ) の木
- n - (a の部分木サイズ) の木
に別れることがわかります。 n - (a の部分木サイズ) が n/2 以下で最大のものを覚えておけばこの中で (a の部分木サイズ) - (v の部分木サイズ) が n/2 以下になるものがあるかは, O(1) でわかります。
・つなげる木が v の祖先でない場合(要するに v の祖先の子孫のうち v の部分木以外のやつ)
木dp するとき dfs から抜け出すタイミングで部分木のサイズのメモしていくと, 頂点 v にたどり着いたときにメモされているのは, v 祖先の子孫の部分木のサイズのみになっています(直接の先祖はまだ v が子にあるので dfs から抜けておらず, サイズがメモされていない)。
よって, 部分木のサイズが n/2 以下なら 部分木のサイズをメモする, というようにやれば同じようにできます。
この手法でやるときは一回 dfs した後もう一回グラフを逆順にして再び dfs しなければいけないことに注意です。
// セグメント木(RMQ 対応) // update: k 番目の値を a に変更 // query: [l, r) の区間の最大値を求める template<typename T> struct ST { vector<T> seg; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(2*size-1, 0); } inline T merge(T x, T y) { return max(x, y); } void update(int k, T a) { k += size-1; seg[k] = a; while (k > 0) { k = (k-1)/2; seg[k] = merge(seg[k*2+1], seg[k*2+2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; const int MAXN = 400400; vi G[MAXN]; // Euler-Tour const int MAXSIZE = MAXN; int BEGIN[MAXSIZE], END[MAXSIZE]; vector<int> euler_tour; int K; void createEulerTour(int v, int p) { BEGIN[v] = K++; euler_tour.push_back(v); for (int el : G[v]) { if (el == p) continue; createEulerTour(el, v); euler_tour.push_back(v); K++; } END[v] = K; } int subSize[MAXN]; pii maxi[MAXN]; int n; int getSize(int v, int p) { int& ret = subSize[v]; pii& ma = maxi[v]; ma.first = 0, ma.second = -1; for (int ch : G[v]) if (ch != p) { int tmp = getSize(ch, v); if (ma.first < tmp) { ma.first = tmp; ma.second = ch; } ret += tmp; } ret++; int tmp = n - ret; if (ma.first < tmp) { ma.first = tmp; ma.second = p; } return ret; } int ans[MAXN]; int tsize; void dfs(int v, int p, ST<int>& seg, int top) { //cout << v << " " << top << " " << tsize << endl; if (maxi[v].second == p) { if (subSize[top]-subSize[v] <= n/2) ans[v] = 1; else if (n-subSize[v]-tsize <= n/2) ans[v] = 1; } else { int ch = maxi[v].second; int tmp = seg.query(BEGIN[ch]+1, END[ch]); if (maxi[v].first - tmp <= n/2) ans[v] = 1; } if (n - subSize[v] <= n/2) top = v; for (int ch : G[v]) if (ch != p) { dfs(ch, v, seg, top); } if (subSize[v] <= n/2) tsize = max(tsize, subSize[v]); } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } // 部分木のサイズを求める getSize(0, -1); // euler tour して部分木のサイズをメモ createEulerTour(0, -1); ST<int> seg(euler_tour.size()); for (int i = 0; i < n; i++) { if (subSize[i] > n/2) { seg.update(BEGIN[i], 0); } else { seg.update(BEGIN[i], subSize[i]); } } dfs(0, -1, seg, 0); tsize = 0; for (int i = 0; i < n; i++) reverse(G[i].begin(), G[i].end()); dfs(0, -1, seg, 0); for (int i = 0; i < n; i++) { cout << ans[i] ; if (i < n-1) cout << " "; } cout << endl; return 0; }
AIM Tech Round 3 (Div. 1) B. Recover the String
問題
0, 1 のみから構成される文字列で, 以下を満たすものを作れ。
- 00 の部分文字列が a00 個ある
- 01 の部分文字列が a01 個ある
- 10 の部分文字列が a10 個ある
- 11 の部分文字列が a11 個ある
連続部分文字列ではないことに注意。
解法
0 が n 個あるとすると, 00 の部分文字列は n*(n-1)/2 個あります。これから n がほとんど一意に決められます(n = 0 と n = 1 は区別できない)。
同様に a11 の情報から 1 の個数 m をほとんど一意に決められます。
0, 1 の区別はめんどくさいので, for 文で n+i, m+j を調べることにしましょう。以下では n, m は一意に確定したとします。
01, 10 の部分文字列は合計で n*m 個あります。a01 の個数から考えていくとすると, 0 の後に 1 が m 個続くようなものがいくつあるか, 1 が m-1 個続くようなものがいくつあるか, というように順番に調べていけば必ず所望の文字列が見つかることが分かります。
const string no = "Impossible"; string calc(vi a, int n, int m) { if (n*(n-1)/2 != a[0]) return no; if (m*(m-1)/2 != a[3]) return no; if (a[1] + a[2] != n*m) { return no; } if (n == 0 && m == 0) return "0"; string ret; for (int i = m; i > 0 && a[1] > 0; i--) { int x = a[1] / i; a[1] %= i; for (int j = 0; j < x; j++) { ret += '0'; n--; } ret += '1'; m--; } for (int i = 0; i < m; i++) ret += '1'; for (int i = 0; i < n; i++) ret += '0'; return ret; } string solve() { vi a(4); for (int i = 0; i < 4; i++) cin >> a[i]; int n = 0; while (n*(n-1)/2 < a[0]) n++; int m = 0; while (m*(m-1)/2 < a[3]) m++; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) { string t = calc(a, n+i, m+j); if (t != no) return t; } return no; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << solve() << endl; return 0; }
AOJ 2439 Hakone
解法
まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。
そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点では何位なのかの場合の数を求めれば良いわけですが, 雰囲気としては以下のような戦略を取ります。
- C[i] = 'D' なら, [0, i) に所望のチーム(順位が落ちてきたチーム)がないとおかしいので, ここで C[i] に対応するチームを確定させる
- C[i] = 'U' なら, まだ所望のチームはどこかよくわからないので, 放っておく
具体的には以下のようにやります。
dp[i][j][k] = (i 番目まで見て, j チームはまだどこに割り当てられるか確定しておらず, k チーム割当先が残っているような場合の数) とします。割当先が残っている k チームというのは, C[l] = 'U' だったようなもので, まだどうしようか決めてないやつですね。
dp[0][0][0] = 1 であり, dp[n][0][0] が求めるべき値です。
このとき, dp[i][j][k] からは以下のように遷移します。
- C[i] == 'D' の時,
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決めるが, i 番目のチームはどこに割り当てるか決めない。
- 割り当て方は, j 通りあるので, dp[i+1][j][k] += dp[i][j][k] * j
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決め, かつ i 番目のチームを k チームのどれかにする。
- 割り当て方は j * k 通りなので, dp[i+1][j-1][k-1] += dp[i][j][k] * j * k
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決めるが, i 番目のチームはどこに割り当てるか決めない。
- C[i] == 'U' の時,
- その i 番目はどこにも割り当てない場合 これは dp[i+1][j+1][k+1] += dp[i][j][k]
- i 番目を今までに割り当てられていない k 個のどれかに割り当てる場合, dp[i+1][j][k] += dp[i][j][k] * k
これで解けます。
ただ上の遷移をよく見ると j = k のところ以外は dp[i][j][k] = 0 となることに気付くので, O(N^2) で解けます。
O(N^2)
const int MAXN = 222; const int MOD = 1e9+7; ll dp[MAXN][MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; string s; for (int i = 0; i < N; i++) { char c; cin >> c; if (c != '-') s += c; } N = s.size(); dp[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) { if (s[i] == 'D') { dp[i+1][j] += dp[i][j] * j % MOD; if (j) dp[i+1][j-1] += dp[i][j] * j * j % MOD; } else { dp[i+1][j+1] += dp[i][j]; dp[i+1][j] += dp[i][j] * j; } } for (int j = 0; j <= i+1; j++) dp[i+1][j] %= MOD; } cout << dp[N][0] << endl; return 0; }
O(N^3)
const int MOD = 1e9+7; ll dp[222][222][222]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; string s; for (int i = 0; i < N; i++) { char c; cin >> c; if (c != '-') s += c; } N = s.size(); dp[0][0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) for (int k = 0; k <= i; k++) { if (s[i] == 'D') { dp[i+1][j][k] += dp[i][j][k] * j % MOD; if (j > 0 && k > 0) dp[i+1][j-1][k-1] += dp[i][j][k] * j * k % MOD; } else { dp[i+1][j+1][k+1] += dp[i][j][k]; dp[i+1][j][k] += dp[i][j][k] * k % MOD; } } for (int j = 0; j <= i+1; j++) for (int k = 0; k <= i+1; k++) { dp[i+1][j][k] %= MOD; } } cout << dp[N][0][0] << endl; return 0; }
Codeforces Round #366 (Div. 2) C. Thor
問題
q 個のクエリが飛んでくる。それぞれのクエリは type, x の二つの整数から構成され,
- type = 1 の時, 種類 x のボールが飛んでくる
- type = 2 の時, 今までに飛んできた種類 x のボールをすべて捨てる
- type = 3 の時, 今まで飛んできたすべてのボールのうち, 最初の x 個のボールを捨てる
それぞれのクエリが投げられた直後, 手元にあるボールの数を求めよ。
解法
D[x]: 種類 x のボールが投げられたタイミングをすべて記録したもの
S[x], T[x]: 種類 x のボールのうち, 手元にあるものの区間([S[x], T[x]) の区間 i について, D[x][i] というボールがある)
memo[i]: i 番目に来たボールはまだ手元にあるか
というようにデータを持っておきます。すると,
- type 1 については, D[x].push_back と T[x]++ でだいたい済む
- type 2 については, [S[x], T[x]) の区間に含まれる i について, memo[D[x][i]] = false にする
- type 3 については, memo[x] までをすべて false にする
ということをやれば良いです。すでに調べたところを二重に調べなければ, これらのクエリはすべて全体として O(Q) で対処可能です。
const int MAXN = 300300; vi D[MAXN]; int S[MAXN], T[MAXN], R[MAXN]; bool memo[MAXN]; int main() { int n, q; scanf("%d %d", &n, &q); int note = 0, ans = 0, last = 0; for (int i = 0; i < q; i++) { int type, x; scanf("%d %d", &type, &x); if (type == 1) { D[x].push_back(note); memo[note] = true; //R[note] = x; note++; ans++; T[x]++; } else if (type == 2) { for (int i = S[x]; i < T[x]; i++) { if (memo[D[x][i]]) { ans--; memo[D[x][i]] = false; } } S[x] = T[x]; } else { for (int i = last; i < x; i++) { if (memo[i]) { ans--; memo[i] = false; //S[R[i]]++; } } last = max(last, x); } printf("%d\n", ans); } return 0; }
これ 2000 人も解けるのね…
AOJ 2397 Three-way Branch
問題
Three-way Branch | Aizu Online Judge
W*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか。
解法
W がまぁまぁ小さくて H が超でかいので行列累乗な感じがします。
障害物は N 個しかないので,
- 障害物のある行になるまでは行列累乗
- 障害物ある行では 対応するところの場合の数を 0 にする
というようにやれば O(W^3 log H * N) でできます。…結構ギリギリですが。
typedef long long number; typedef vector<number> vec; typedef vector<vec> matrix; const int MOD = 1e9+9; // O( n ) matrix Identity(int n) { matrix A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n^3 ) matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), vec(B[0].size())); for (int i = 0; i < (int)C.size(); ++i) for (int j = 0; j < (int)C[i].size(); ++j) for (int k = 0; k < (int)A[i].size(); ++k) { C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } return C; } // O( n^3 log e ) matrix pow(const matrix &A, ll e) { if (e == 0) return Identity(A.size()); if (e == 1) return A; if (e % 2 == 0) { matrix tmp = pow(A, e/2); return mul(tmp, tmp); } else { matrix tmp = pow(A, e-1); return mul(A, tmp); } } // O(n) number tr(const matrix &A) { number ans = 0; for (int i = 0; i < (int)A.size(); ++i) ans += A[i][i]; return ans; } // O( n ) number inner_product(const vec &a, const vec &b) { number ans = 0; for (int i = 0; i < (int)a.size(); ++i) ans += a[i] * b[i]; return ans; } // O( n^2 ) vec mul(const matrix &A, const vec &x) { vec y(A.size()); for (int i = 0; i < (int)A.size(); ++i) for (int j = 0; j < (int)A[0].size(); ++j) (y[i] += (A[i][j] * x[j] % MOD)) %= MOD; return y; } const int MAXN = 33; int W, N; ll H; ll solve() { vector<pair<ll, int> > P(N); for (int i = 0; i < N; i++) { cin >> P[i].second >> P[i].first; P[i].first--; P[i].second--; } sort(P.begin(), P.end()); vec v(W); v[0] = 1; ll now = 0; for (int i = 0; i < N; ) { matrix mat(W, vec(W)); for (int j = 0; j < W; j++) { if (j-1 >= 0) mat[j][j-1] = 1; mat[j][j] = 1; if (j+1 < W) mat[j][j+1] = 1; } v = mul(pow(mat, P[i].first-now), v); now = P[i].first; int ni = i; while (ni < N && P[i].first == P[ni].first) ni++; for (int j = i; j < ni; j++) v[P[j].second] = 0; i = ni; } matrix mat(W, vec(W)); for (int i = 0; i < W; i++) { if (i-1 >= 0) mat[i][i-1] = 1; mat[i][i] = 1; if (i+1 < W) mat[i][i+1] = 1; } v = mul(pow(mat, H-1-now), v); return v[W-1]; } int main() { cin.tie(0); ios::sync_with_stdio(false); for (int t = 1; ; t++) { cin >> W >> H >> N; if (W == 0) break; cout << "Case " << t << ": " << solve() << endl; } return 0; }
