SRM406 Div2 Hard

1000

DPする。
dp [ i ] [ j ] = i から j までの間で作れるパターン数

意外と難しかった。

view plainprint?

1. vector<int> C;  
2. int N;  
3.   
4. const int M = 50 + 1;  
5.   
6. lli memo[M][M];  
7.   
8. const lli mod = 100000007;  
9.   
10. // [... a, b, ...]  
11. bool next(int a, int b)  
12. {  
13.   return (a + 1) % N == b;  
14. }  
15.   
16. lli rec(int i, int j)  
17. {  
18.   if (next(i, j)) return 1;  
19.    
20.   lli &ret = memo[i][j];  
21.   if (ret != -1) return ret;  
22.   
23.   lli sum = rec(i + 1, j);  
24.    
25.   for (int k = i + 2; k < j; ++k) {  
26.     if (C[i] != C[k]) {  
27.       sum += rec(i, k) * rec(k, j) / 2LL;  
28.       sum %= 2LL * mod;  
29.     }  
30.   }  
31.   
32.   if (C[i] != C[j] && !next(i, j) && !next(j, i)) {  
33.     sum *= 2LL;  
34.     sum %= 2LL * mod;  
35.   }  
36.   
37.   return ret = sum;  
38. }  
39.   
40. class PolygonColors {  
41. public:  
42.   int getWays(int N_, vector <int> C_)  
43.   {  
44.     N = N_;  
45.     C = C_;  
46.   
47.     for (int i = 0; i < (int)N; ++i) {  
48.       int j = (i + 1) % C.size();  
49.       if (C[i] == C[j]) return 0;  
50.     }  
51.   
52.     fill(&memo[0][0], &memo[M - 1][M], -1);  
53.     return rec(0, N - 1) % mod;  
54.   }  
55. };  

vector<int> C;
int N;

const int M = 50 + 1;

lli memo[M][M];

const lli mod = 100000007;

// [... a, b, ...]
bool next(int a, int b)
{
  return (a + 1) % N == b;
}

lli rec(int i, int j)
{
  if (next(i, j)) return 1;
 
  lli &ret = memo[i][j];
  if (ret != -1) return ret;

  lli sum = rec(i + 1, j);
 
  for (int k = i + 2; k < j; ++k) {
    if (C[i] != C[k]) {
      sum += rec(i, k) * rec(k, j) / 2LL;
      sum %= 2LL * mod;
    }
  }

  if (C[i] != C[j] && !next(i, j) && !next(j, i)) {
    sum *= 2LL;
    sum %= 2LL * mod;
  }

  return ret = sum;
}

class PolygonColors {
public:
  int getWays(int N_, vector <int> C_)
  {
    N = N_;
    C = C_;

    for (int i = 0; i < (int)N; ++i) {
      int j = (i + 1) % C.size();
      if (C[i] == C[j]) return 0;
    }

    fill(&memo[0][0], &memo[M - 1][M], -1);
    return rec(0, N - 1) % mod;
  }
};