950 PT:
題意：
給三種顏色的蛋糕A、B、C，每種有a,b,c個，共n個。
要把n個蛋糕放成一圈，相鄰的兩個顏色不能相同。
思路：
DP：記憶化搜索！ dp[n][s[0]][s[1]][d][l]表示：還需要放n個，第一種還有s[0]個，第二種還有s[1]個，當前放的是第d種，最后一個是l種的方案數。
f(n,s,d,l)求還有n個需要放，當前放的是第d種，最后一個放的是第l種。s是個數數組。
#define mod 1000000007
#define maxn 52
using namespace std;
long long dp[maxn][maxn][maxn][3][3];
class ColorfulCupcakesDivTwo{
public:
long long f(int n,int s[],int d,int l){
if (n==0 && d!=l)
return 1;
if (n==0)
return 0;
if (dp[n][s[0]][s[1]][d][l]!=-1)
dp[n][s[0]][s[1]][d][l];
long long ans=0;
for (int i=0;i<3;i++)
if (i!=d && s[i])
{
s[i]--;
ans+=f(n-1,s,i,l);
ans %=mod;
s[i]++;
}
return dp[n][s[0]][s[1]][d][l]=ans;
}
int countArrangements(string cupcakes){
memset(dp,-1,sizeof(dp));
int s[3]={0,0,0};
int N=cupcakes.length();
for (int i=0;i<N;i++)
s[cupcakes[i]-'A']++;
long long ans=0;
for (int i=0;i<3;i++)
if (s[i])
{
s[i]--;
ans+=f(N-1,s,i,i);
ans %=mod;
s[i]++;
}
return ans;
}
};