$N$ 個のカップケーキがあり、色は3色のうちのどれかです。
円卓に座っている $N$ 人に「となりの人とは違う色のカップケーキにする」というルールにもとづいて $1$ 人に $1$ 個配るとき、
配り方のパターン数を求めてください。SRM 551 Div2 Hard
$3 \le N \le 50$

#include <iostream>
#include <algorithm>
using namespace std;

class ColorfulCupcakesDivTwo { public: int countArrangements(string cupcakes); };
const int mod = int(1e9) + 7;
int n;
vector<int> cs;
vector<vector<vector<vector<vector<int>>>>> dp;

// 手元の「色0」がc0個、「色1」がc1個、「色2」がc2個。
// 最初の人の色がfirst、最後の人(最新の人と言ったほうがいいかも)の色がlast
int rec(int c0, int c1, int c2, int first, int last) {
  int &res = dp[c0][c1][c2][first][last];
  // 手元にもう無いときは、最後の人と最初の人が違う色なら1通り。同じ色なら0通り
  if(c0==0 && c1==0 && c2==0) { return res = first!=last; }
  if(res != -1) { return res; }
  res = 0;
  // まだ誰にも置いてないとき
  if(first == 3) {
    if(c0) { res = (res + rec(c0-1, c1, c2, 0, 0)) % mod; } // 「色0」がまだ手元にあるなら(=if(c0))それを置く。最初も最新も「色0」になる。
    if(c1) { res = (res + rec(c0, c1-1, c2, 1, 1)) % mod; }
    if(c2) { res = (res + rec(c0, c1, c2-1, 2, 2)) % mod; }
  // もう置いてるとき
  } else {
    if(c0 && last!=0) { res = (res + rec(c0-1, c1, c2, first, 0)) % mod; } // 「色0」が手元にあって前の人が「色0」でないときは「色0」を置く。
    if(c1 && last!=1) { res = (res + rec(c0, c1-1, c2, first, 1)) % mod; }
    if(c2 && last!=2) { res = (res + rec(c0, c1, c2-1, first, 2)) % mod; }
  }
  return res;
}

int ColorfulCupcakesDivTwo::
countArrangements(string cupcakes) {
  n = cupcakes.size();
  cs.resize(3);
  for(char ch : cupcakes) { cs[ch-'A']++; }
  int c0 = cs[0], c1 = cs[1], c2 = cs[2];
  dp.assign(n, vector<vector<vector<vector<int>>>>(n, vector<vector<vector<int>>>(n, vector<vector<int>>(4, vector<int>(4, -1)))));
  int res = rec(c0, c1, c2, 3, 3) % mod;
  return res;
}
    

#include <iostream>
#include <algorithm>
using namespace std;

class ColorfulCupcakesDivTwo { public: int countArrangements(string cupcakes); };
const int mod = int(1e9) + 7;
int n;
vector<int> cs;
vector<vector<vector<vector<vector<int>>>>> dp;

int ColorfulCupcakesDivTwo::
countArrangements(string cupcakes) {
  n = cupcakes.size();
  cs.resize(3);
  for(char ch : cupcakes) { cs[ch-'A']++; }
  int c0 = cs[0], c1 = cs[1], c2 = cs[2];
  dp.assign(n, vector<vector<vector<vector<int>>>>(n, vector<vector<vector<int>>>(n, vector<vector<int>>(3, vector<int>(3, 0)))));
  // 1個置いたときは1通り
  dp[1][0][0][0][0] = 1;
  dp[0][1][0][1][1] = 1;
  dp[0][0][1][2][2] = 1;
  for(int c0=0; c0<n; c0++) {
    for(int c1=0; c1<n; c1++) {
      for(int c2=0; c2<n; c2++) {
        if(c0 + c1 + c2 <= 1) { continue; } // 2個めを置くときからを考える
        for(int first=0; first<3; first++) {
          // 「色0」が置けるのは、手元に「色0」があり、前に置いたのが「色0」でないとき
          if(c0) { dp[c0][c1][c2][first][0] = (dp[c0-1][c1][c2][first][1] + dp[c0-1][c1][c2][first][2]) % mod; }
          if(c1) { dp[c0][c1][c2][first][1] = (dp[c0][c1-1][c2][first][2] + dp[c0][c1-1][c2][first][0]) % mod; }
          if(c2) { dp[c0][c1][c2][first][2] = (dp[c0][c1][c2-1][first][0] + dp[c0][c1][c2-1][first][1]) % mod; }
        }
      }
    }
  }
  int res = 0;
  for(int first=0; first<3; first++) {
    for(int last=0; last<3; last++) {
      if(first==last) { continue; }
      res = (res + dp[c0][c1][c2][first][last]) % mod;
    }
  }
  return res;
}