Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory
J君，O君，I君がいるかいないかを3ビットで持つ．
とする．
この条件を満たす場合に遷移可能．．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <bitset>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define MOD 10007
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
ll dp [ 1005 ][ 8 ];
int main () {
int n ;
cin >> n ;
string s ;
cin >> s ;
map < char , int > id ;
id [ 'J' ] = 2 ; id [ 'O' ] = 1 , id [ 'I' ] = 0 ;
memset ( dp , 0 , sizeof ( dp ));
dp [ 0 ][ 1 << 2 ] = 1 ;
REP ( i , 1 , n + 1 ) {
int d = id [ s [ i - 1 ] ];
rep ( j , 1 << 3 ) {
if ( ! ( j & ( 1 << d ))) continue ;
rep ( k , 1 << 3 ) {
if ( j & k ) {
dp [ i ][ j ] += dp [ i - 1 ][ k ];
dp [ i ][ j ] %= MOD ;
}
}
}
}
ll ans = 0 ;
rep ( i , 1 << 3 ) {
ans += dp [ n ][ i ];
}
cout << ans % MOD << endl ;
return 0 ;
}