SDUT: 2879 Colorful Cupcakes(DP 계수)

제목: 세 가지 색깔의 구슬을 고리로 둘러싸고 두 개의 구슬과 서로 다른 색깔을 요구하며 모두 몇 가지 상황이 있는지 물어본다.
사고방식: 가방 계수 문제.먼저 고리를 하나의 체인으로 볼 수 있다. dp[i][j][k][l], i는 i가지 색깔을 끝으로 하고 j, k, l는 각각 세 가지 색깔의 구슬이 몇 개인지 나타낸다.체인이라면 상태 이동 방정식을 구축하기 쉽다.링은 처음과 끝의 위치를 고려해야 한다. 사실상 답안 dp[0][v0][v1][v2]와 같은 0번째 색깔로 시작하는 모든 상황을 빼려면 dp[0][1][0][0][0]을 0으로 초기화하면 된다.다른 두 가지 상황은 같은 이치이다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
const int maxn=55;
LL dp[3][maxn][maxn][maxn];
int V[3];
int n;
void DP()
{
    for(int i=0; i<=V[0]; ++i)
        for(int j=0; j<=V[1]; ++j)
        {
            for(int k=0; k<=V[2]; ++k)
            {
                for(int l=0; l<3; ++l)
                {
                    if(l==0)
                    {
                        dp[1][i][j+1][k]+=dp[0][i][j][k];
                        dp[2][i][j][k+1]+=dp[0][i][j][k];
                    }
                    else if(l==1)
                    {
                        dp[0][i+1][j][k]+=dp[1][i][j][k];
                        dp[2][i][j][k+1]+=dp[1][i][j][k];
                    }
                    else if(l==2)
                    {
                        dp[0][i+1][j][k]+=dp[2][i][j][k];
                        dp[1][i][j+1][k]+=dp[2][i][j][k];
                    }
                    dp[0][i+1][j][k]%=mod;
                    dp[1][i][j+1][k]%=mod;
                    dp[2][i][j][k+1]%=mod;
                }
            }
        }

}
LL solve()
{
    LL ans=0;
    memset(dp,0,sizeof(dp));
    dp[0][1][0][0]=0;
    dp[1][0][1][0]=(V[1]>=1)?1:0;
    dp[2][0][0][1]=(V[2]>=1)?1:0;
    DP();
    ans+=dp[0][V[0]][V[1]][V[2]];
    ans%=mod;

    memset(dp,0,sizeof(dp));
    dp[0][1][0][0]=(V[0]>=1)?1:0;
    dp[1][0][1][0]=0;
    dp[2][0][0][1]=(V[2]>=1)?1:0;
    DP();
    ans+=dp[1][V[0]][V[1]][V[2]];
    ans%=mod;

    memset(dp,0,sizeof(dp));
    dp[0][1][0][0]=(V[0]>=1)?1:0;
    dp[1][0][1][0]=(V[1]>=1)?1:0;
    dp[2][0][0][1]=0;
    DP();
    ans+=dp[2][V[0]][V[1]][V[2]];
    ans%=mod;
    return ans;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(V,0,sizeof(V));
        char s[300];
        cin>>s;
        n=strlen(s);
        for(int i=0; s[i]; ++i)
            V[s[i]-'A']++;
        cout<<solve()<<endl;
    }
    return 0;
}