Source上げるゾ

4.cpp

#include <cstdio>

using namespace std;

#define J 1
#define O 2
#define I 4

int need[1000];
int dp[8][1000];

int main() {
    int i;
    int n;
    int sum = 0;

    scanf("%d", &n);

    for (i=0;i<n;i++) {
        int j;
        for (j=0;j<8;j++) {
            dp[j][i] = 0;
        }
    }

    need[0] |= J;
    for (i=0;i<n;i++) {
        char c;
        scanf(" %c", &c);
        printf("%c\n", c);
        switch (c) {
        case 'J':
            need[i] |= J;
            break;
        case 'O':
            need[i] |= O;
            break;
        case 'I':
            need[i] |= I;
            break;
        }
    }

    for (i=0;i<8;i++) {
        dp[need[0] | i][0] = 1;
    }

    for (i=1;i<n;i++) {
        int j;
        int has_calced[8];
        for (j=0;j<8;j++) {
            has_calced[j] = 0;
        }

        for (j=0;j<8;j++) {
            int k;

            if (has_calced[need[i] | j]) continue;
            has_calced[need[i] | j] = 1;

            for (k=0;k<8;k++) {
                if ((need[i] | j) & k) {
                    dp[need[i] | j][i] += dp[k][i-1];
                    dp[need[i] | j][i] %= 10007;
                }
            }
        }
    }

    for (i=0;i<8;i++) sum += dp[i][n-1];
    sum %= 10007;
    printf("%d\n", sum);
}