CF17C Balance(시퀀스 로봇 + 카운트 dp)

Description

a b c로 구성된 문자열 S S S S를 지정하면 두 개의 인접 문자를 선택하여 첫 번째 문자로 두 번째 문자를 덮어쓰거나 두 번째 문자로 첫 번째 문자를 덮어쓸 수 있습니다.몇 개의 다른 문자열이 변할 수 있는지 구하고a b c의 개수는 2량차≤1\leq1≤1로 51123987511239875112398751123987에 대해 모형을 취한다.
1 ≤ ∣ S ∣ ≤ 150 1\leq |S|\leq 150 1≤∣S∣≤150.

Solution

시퀀스 로봇 + dp.변환된 문자열을 T T T 로 만들고, 압축 문자열을 T ′ T 'T' 로 하고, aabcccbbaa 의 압축 문자열을 abcba 로 하면 무게를 빼는 것과 같다.그러면 조작한 후 얻은 T′T'T′는 반드시 SS의 서열이다. 한 자모를 앞으로 뒤로 옮기려면 앞뒤 자모를 덮어써야 하기 때문에 SS에서 두 자모의 상대적인 순서를 뒤바꾸지 않고 그 중 한 자모만 덮어쓰거나 유지할 수 있다.
그래서 T′T'T′의 자모는 S S S S와 일치할 수 있다.영fi,a,b,cf{i, a, b, c} fi, a, b, c는, T′T'T′와 S i Si Si가 일치합니다. 이때 T T Ta b c에 a, b, c a,\b,\c a, b, c가 나타날 때 몇 개의 다른 T T가 있습니까?Tip: f f 의 정의는 S i S 에 이르지 않습니다.i Si, a b c 발생 횟수 대신 S i S 일치i Si​.예를 들어 샘플4 abca.f 1 , 2 , 0 , 0 = 1 f_{1,2,0,0} = 1 f1,2,0,0=1이 맞습니다. T T T 중 두 개a가 모두 S 1 S 이기 때문입니다.1, S1이 바뀌었어.
n≤150n\leq150n≤150이므로 i,a,b,ci,\a,\b,\ci,a,\ci,a,b,c를 4차원으로 열거할 수 있습니다.a + b + c = n ∧ a + b + c = n\land a+b+c=n ∧ a - b, a - a - a - c, a - a - c, a - a - a - c, a - a - b, a - a - c,\| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\| | | | | | | | | | | | | | | | | |\| | | |\|\\\, a, b, c f{i,a,b,c}fi,a,b,c가 답안을 계산합니다.그럼 어떻게 옮겨요?
S i S_i Si가 "다른 문자를 덮어쓰려는 경우"그러면 이것부터 덮어쓰면 됩니다. 예를 들어 $Si = $ a , f i , a + 1 , b , c = f i , a + 1 , b , c + f i , a , b , c f_{i,a+1,b,c} = f_{i,a+1,b,c} + f_{i,a,b,c} fi,a+1,b,c​=fi,a+1,b,c​+fi,a,b,c​.a,b,c a,\b,\c a,b,c를 열거하고 있기 때문에 fi,a+j,b,c f 로 이동합니다.{i, a + j, b, c} fi,a+j,b,c​. S i S_iSi가'덮어쓸 알파벳'인 경우 다른 알파벳을 덮어쓸 알파벳으로 이동하면 됩니다.
'다른 알파벳을 덮어쓸 것' 을 어떻게 정합니까? 만약 그 알파벳의 아래 표시를 일일이 열거해서 정한다면, 답안을 반복해서 계산할 수 있습니다.예를 들어 S S = caba, 그 중 하나의 T T T는 aaaa이면 ∑i = 1∣S ∣ f i, 4, 0, 0 = 1\sum 이다.{i=1}^{|S|} f_{i,4,0,0}= 1∑i=1∣S∣fi,4,0,0=1,매개 아래 ∑i=1∣S∣fi,4,0,0=1\sum{i=1}^{|S|} f_{i, 4,0,0} = 1∑i=1∣S∣fi, 4,0,0=1은 222로 각각 i=2, 4i=2,\4i=2, 4i=2, 4.i=2 i=2 i=2의a가 c와ba를 덮어쓰면 i=4 i=4의a는 덮어쓸 필요가 없다cab.
그래서 nxti, jnxt 를 미리 처리할 수 있습니다{i, j} nxti, j는 n x t i, j≥i ∧ S n x t i, j = j nxt{i,j}\ge i\land S_{nxt_{i,j}} = j nxti,j​≥i∧Snxti,j​​=j.즉 ii i 후 첫 번째 자모 jj에 나타난 하표, ii를 포함한다.전이 방정식은 다음과 같다.
f 1 , 0 , 0 , 0 = 1 f_{1,0,0,0} = 1 f1,0,0,0​=1
f n x t i , 0 , a + 1 , b , c = f n x t i , 0 , a + 1 , b , c + f i , a , b , c f_{nxt_{i,0}, a + 1, b, c} = f_{nxt_{i,0}, a + 1, b, c} + f_{i,a,b,c} fnxti,0​,a+1,b,c​=fnxti,0​,a+1,b,c​+fi,a,b,c​
f n x t i , 1 , a , b + 1 , c = f n x t i , 1 , a , b + 1 , c + f i , a , b , c f_{nxt_{i,1}, a, b + 1, c} = f_{nxt_{i,1}, a, b + 1, c} + f_{i,a,b,c} fnxti,1​,a,b+1,c​=fnxti,1​,a,b+1,c​+fi,a,b,c​
f n x t i , 2 , a , b , c + 1 = f n x t i , 2 , a , b , c + 1 + f i , a , b , c f_{nxt_{i,2}, a, b, c + 1} = f_{nxt_{i,2}, a, b, c + 1} + f_{i,a,b,c} fnxti,2​,a,b,c+1​=fnxti,2​,a,b,c+1​+fi,a,b,c​
문자마다 n+23\rac{n+2} {3} 3n+2를 초과하지 않기 때문에 시공 복잡도는 O(n 4 27)O(\rac{n^4} {27}) O(27n4)입니다.

Code

#include 
using namespace std;
const int N = 150 + 5, p = 51123987;
char s[N];
int f[N][(N + 2) / 3][(N + 2) / 3][(N + 2) / 3], nxt[N][3], n, ans;
int main() {
    scanf("%d%s", &n, s + 1);
    nxt[n + 1][0] = nxt[n + 1][1] = nxt[n + 1][2] = n + 1;
    for(int i = n; i >= 1; i--) {
        nxt[i][0] = nxt[i + 1][0];
        nxt[i][1] = nxt[i + 1][1];
        nxt[i][2] = nxt[i + 1][2];
        if(s[i] == 'a') nxt[i][0] = i;
        if(s[i] == 'b') nxt[i][1] = i;
        if(s[i] == 'c') nxt[i][2] = i;
    }
    f[1][0][0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int a = 0; a <= (n + 2) / 3; a++)
            for(int b = 0; b <= (n + 2) / 3; b++)
                for(int c = 0; c <= (n + 2) / 3; c++)
                {
                    if(a + b + c == n && abs(a - b) <= 1 && abs(a - c) <= 1 && abs(b - c) <= 1) 
                    	ans = (ans + f[i][a][b][c]) % p; 
                    f[nxt[i][0]][a + 1][b][c] = (f[nxt[i][0]][a + 1][b][c] + f[i][a][b][c]) % p;
                    f[nxt[i][1]][a][b + 1][c] = (f[nxt[i][1]][a][b + 1][c] + f[i][a][b][c]) % p;
                    f[nxt[i][2]][a][b][c + 1] = (f[nxt[i][2]][a][b][c + 1] + f[i][a][b][c]) % p;
                }
    printf("%d
", ans);
    return 0;
}