シフト制

問題

const int MOD = 10007;
const int MAX_N = 1010;

int N;
char S[MAX_N];

int dp[MAX_N][8];

//文字→数字
int char_to_id(char c)
{
	switch (c) {
	case 'J': return 0;
	case 'O': return 1;
	case 'I': return 2;
	}
	return -1;
}

//p番を取り除く
void exclude(int pos, int p)
{
	for (int i = 0;i < 8;i++) if ((i & (1 << p)) == 0) dp[pos][i] = 0;
}

int main()
{
	scanf("%d%s", &N, S); //人数、文字列(参加必須の人)

	for (int i = 0;i < N;i++) {
		if (i == 0) {
			for (int j = 0;j < 8;j++) dp[i][j] = 1;

			exclude(i, 0); //最初 0番 が鍵を持っているため
		}
		else {
			for (int j = 0;j < 8;j++) dp[i][j] = 0;

			for (int j = 0;j < 8;j++)
				for (int k = 0;k < 8;k++) if (j & k) //同じ人が被っていれば
					dp[i][k] = (dp[i][k] + dp[i - 1][j]) % MOD;
		}

		exclude(i, char_to_id(S[i])); //参加必須の人
	}

	int sol = 0;
	for (int i = 0;i < 8;i++) sol = (sol + dp[N - 1][i]) % MOD;

	printf("%d\n", sol);

	return 0;
}