JMC 2014 4番

pastaっぽいと思った。作問のプロだと感じた(小並感)

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int dp[128][128][2];
bool m[128][128];
const int MOD = 100000;

int main() {
	int N, M, L, a, b;
	cin >> N >> M >> L;

	for(int i = 0; i < L; i++) {
		cin >> a >> b;
		a--, b--;
		m[a][b] = true;
	}

	for(int i = 0; i < M; i++) {
		if(!m[0][i]) dp[0][i][0] = 1;
	}


	for(int i = 0; i < N - 1; i++) { 
		for(int j = 0; j < M; j++) {
			for(int k = 0; k < 2; k++) {
				if(k == 0) {
					if(m[i + 1][j]) continue;
					dp[i + 1][j][!k] += dp[i][j][k];
					dp[i + 1][j][!k] %= MOD;
				} else {
					for(int l = 0; l < M; l++) {
						if(m[i + 1][l]) continue;
						a = (l == j ? k : !k);
						dp[i + 1][l][a] += dp[i][j][k];
						dp[i + 1][l][a] %= MOD;
					}
				}
			}
		}
	}

	int ans = 0;

	for(int i = 0; i < M; i++) {
		ans += dp[N - 1][i][1];
		ans %= MOD;
	}

	cout << ans<< endl;
}