CF17C Balance

定義壓縮串為把某字元串中所有連續相同的字母壓縮成一個所形成的的串。如aabbaaaabcc -> ababc

如果原串是A，變形後的串為B，那麼A的壓縮串A‘和B的壓縮串B'，存在這樣的關系：B'一定是A’的字串。

預處理統計A中每個字元後面（包括自身，因為可以不斷重複自己）最近的'a''b''c'分别在哪個位置，用next[i][0-2]記錄。

從1-n生成新串B，用dp[i][a][b][c]記錄處理到A中第i個字元（其實跟i沒關系，主要是那個字元，i隻是記錄順序）時，字元串B中存在a個'a',b個'b',c個'c'時的方案數。

并且下一個狀态可以轉移到dp[next[i][0]][a+1][b][c]或dp[next[i][1]][a][b+1][c]或dp[next[i][2]][a][b][c+1]，最後判斷一下終止狀态：a+b+c==0且a,b,c相差不超過1。

注意總長度為n時，實際上每個字元的出現次數不可能超過(n+2)/3，是以算法最多計算150*50*50*50次，雖說是O(n^4)，但還可以接受。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
using namespace std;

const int mod = 51123987;
int n,lim;
char str[155];
int next[155][3];
int dp[155][55][55][55];
int ans;

int main()
{
    while (scanf("%d",&n)==1)
    {
        scanf("%s",str+1);
        next[n+1][0]=next[n+1][1]=next[n+1][2]=n+1;
        for (int i=n;i>=1;i--)
        {
            next[i][0]=next[i+1][0];
            next[i][1]=next[i+1][1];
            next[i][2]=next[i+1][2];
            if (str[i]=='a') next[i][0]=i;
            if (str[i]=='b') next[i][1]=i;
            if (str[i]=='c') next[i][2]=i;
        }
        ans=0;
        lim=(n+2)/3;
        memset(dp,0,sizeof(dp));
        dp[1][0][0][0]=1;
        for (int i=1;i<=n;i++)
            for (int a=0;a<=lim;a++)
                for (int b=0;b<=lim;b++)
                    for (int c=0;c<=lim;c++)
                    {
                        if (a+b+c==n && abs(a-b)<=1 && abs(a-c)<=1 && abs(b-c)<=1)
                        {
                            ans=(ans+dp[i][a][b][c])%mod;
                            continue;
                        }
                        if (next[i][0]<=n) dp[next[i][0]][a+1][b][c]=(dp[next[i][0]][a+1][b][c]+dp[i][a][b][c])%mod;
                        if (next[i][1]<=n) dp[next[i][1]][a][b+1][c]=(dp[next[i][1]][a][b+1][c]+dp[i][a][b][c])%mod;
                        if (next[i][2]<=n) dp[next[i][2]][a][b][c+1]=(dp[next[i][2]][a][b][c+1]+dp[i][a][b][c])%mod;
                    }
        printf("%d\n",ans);
    }
	return 0;
}