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