Submission #1583801

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define INF 999999999

typedef long long ll;
typedef pair<int, string> P;

const int MOD = 10000;
int n, k, cnt;
int c[110];
int dp[110][4][4];

int main(){
	cin.tie(0);
  ios::sync_with_stdio(false);

	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		c[a-1] = b;
	}
	if (c[0] != 0) {
		dp[0][0][c[0]] = 1;
	}
	else {
		dp[0][0][1] = 1;
		dp[0][0][2] = 1;
		dp[0][0][3] = 1;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 1; k < 4; k++) {
				if (j == k && c[i] == k) continue;
				if (c[i] != 0) dp[i][k][c[i]] += dp[i-1][j][k] % MOD;
				else {
					for (int x = 1; x < 4; x++) {
						if (j == k && k == x) continue;
						dp[i][k][x] += dp[i-1][j][k] % MOD;
					}
				}
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cnt += dp[n-1][i][j];
		}
	}

	cout << cnt % MOD << endl;

	return 0;
}

Submission Info

Judge Result