SRM551 Div2 Hard

950

memo[最初に選んだヤツ][最後に選んだヤツ][残りのA][残りのB][残りのC]

view plainprint?

1. const int N = 50 + 1;  
2. const int A = 0, B = 1, C = 2, D = 3;  
3. const int LAST = 4, FIRST = 4;  
4.   
5. lli memo[FIRST][LAST][N][N][N];  
6.   
7. const lli mod = 1000000007;  
8.   
9. lli rec(int first, int last, int a, int b, int c)  
10. {  
11.   lli &ret = memo[first][last][a][b][c];  
12.   if (ret != -1) return ret;  
13.   if (a == 0 && b == 0 && c == 0) {  
14.     return last != first;  
15.   }  
16.   
17.   lli sum = 0;  
18.   
19.   if (first == D) {  
20.     if (a) sum = (sum + rec(A, A, a - 1, b, c)) % mod;  
21.     if (b) sum = (sum + rec(B, B, a, b - 1, c)) % mod;  
22.     if (c) sum = (sum + rec(C, C, a, b, c - 1)) % mod;  
23.   } else {  
24.     if (last == A) {  
25.       if (b) sum = (sum + rec(first, B, a, b - 1, c)) % mod;  
26.       if (c) sum = (sum + rec(first, C, a, b, c - 1)) % mod;  
27.     }  
28.     if (last == B) {  
29.       if (a) sum = (sum + rec(first, A, a - 1, b, c)) % mod;  
30.       if (c) sum = (sum + rec(first, C, a, b, c - 1)) % mod;  
31.     }  
32.     if (last == C) {  
33.       if (a) sum = (sum + rec(first, A, a - 1, b, c)) % mod;  
34.       if (b) sum = (sum + rec(first, B, a, b - 1, c)) % mod;  
35.     }  
36.   }  
37.   
38.   return ret = sum;  
39. }  
40.   
41. class ColorfulCupcakesDivTwo {  
42. public:  
43.   int countArrangements(string C)  
44.   {  
45.     int a = count(C.begin(), C.end(), 'A');  
46.     int b = count(C.begin(), C.end(), 'B');  
47.     int c = count(C.begin(), C.end(), 'C');  
48.   
49.     fill(&memo[0][0][0][0][0], &memo[FIRST][0][0][0][0], -1);  
50.     return rec(D, D, a, b, c) % mod;  
51.   }  
52. };  

const int N = 50 + 1;
const int A = 0, B = 1, C = 2, D = 3;
const int LAST = 4, FIRST = 4;

lli memo[FIRST][LAST][N][N][N];

const lli mod = 1000000007;

lli rec(int first, int last, int a, int b, int c)
{
  lli &ret = memo[first][last][a][b][c];
  if (ret != -1) return ret;
  if (a == 0 && b == 0 && c == 0) {
    return last != first;
  }

  lli sum = 0;

  if (first == D) {
    if (a) sum = (sum + rec(A, A, a - 1, b, c)) % mod;
    if (b) sum = (sum + rec(B, B, a, b - 1, c)) % mod;
    if (c) sum = (sum + rec(C, C, a, b, c - 1)) % mod;
  } else {
    if (last == A) {
      if (b) sum = (sum + rec(first, B, a, b - 1, c)) % mod;
      if (c) sum = (sum + rec(first, C, a, b, c - 1)) % mod;
    }
    if (last == B) {
      if (a) sum = (sum + rec(first, A, a - 1, b, c)) % mod;
      if (c) sum = (sum + rec(first, C, a, b, c - 1)) % mod;
    }
    if (last == C) {
      if (a) sum = (sum + rec(first, A, a - 1, b, c)) % mod;
      if (b) sum = (sum + rec(first, B, a, b - 1, c)) % mod;
    }
  }

  return ret = sum;
}

class ColorfulCupcakesDivTwo {
public:
  int countArrangements(string C)
  {
    int a = count(C.begin(), C.end(), 'A');
    int b = count(C.begin(), C.end(), 'B');
    int c = count(C.begin(), C.end(), 'C');

    fill(&memo[0][0][0][0][0], &memo[FIRST][0][0][0][0], -1);
    return rec(D, D, a, b, c) % mod;
  }
};