Submission #1576006

---

Source Code Expand

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

#define INF 0x3f3f3f3f
#define MOD 10000

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

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

	int n, k;
	cin >> n >> k;
	int d[101] = {};
	int a, b;
	for (int i = 0; i < k; i++) {
		cin >> a >> b;
		d[a-1] = b;
	}
	int dp[101][4][4] = {{{}}};
	if (d[0] != 0) dp[0][0][d[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 (d[i] != 0) {
					if (!(j == k && k == d[i])) dp[i][k][d[i]] += dp[i-1][j][k]%MOD;
				}
				else {
					for (int m = 1; m < 4; m++) {
						if (j == k && k == m) continue;
						dp[i][k][m] += dp[i-1][j][k]%MOD;
					}
				}
			}
		}
	}
	int o = 0;
	for (int j = 0; j < 4; j++)
		for (int i = 0; i < 4; i++) o += dp[n-1][j][i];

	cout << o % MOD << endl;

	return 0;
}

Submission Info

Judge Result