51nod1313 完美串

2024-02-21 08:17:22

一个N长的字符串S（N<=3000），只由'R','G','B'三种字符组成，即串中不存在除了这3个字符以外的其他字符。字符串S的子串substr(L，R)指S[L]S[L+1]S[L+2]..S[R]构成的字符串，其中0<=L<=R<N。称一个字符串为“完美串”，当且仅当该串中存在K个连续的'G'字符。问，存在多少个不同的四元组(a,b,c,d)满足substr(a,b)+substr(c,d)是完美串，其中，0 <= a <= b < c <= d < N。

说明：字符串A和字符串B的+运算指将B连在A的后面，即A+B=AB,如“RRG”+“GBB”=“RRGGBB”。

例如：S="GRG",K=2,因为S中一共就2个'G',而要求K=2，所以只有1个四元组（0,0,2,2）成立，即"G"+"G"="GG".

Input

第一行一个整数K，1<=K<=3000.

第二行一个字符串S，1<=len（S）<=3000,且只由'R','G','B'三种字符组成。

Output

一个整数，即不同的四元组(a,b,c,d)的个数。

容斥+dp，

ans=([a,b]存在k个连续的'G'，[c,d]任意的方案数)+([c,d]存在k个连续的'G'，[a,b]任意的方案数)-([a,b],[c,d]都存在k个连续的'G'的方案数)+([a,b],[c,d]都不存在k个连续的'G'，但拼起来之后存在k个连续的'G'的方案数)

#include<cstdio>

#include<cstring>

char s[];

int n,k;

long long ans=;

int ls[],rs[];

short cl[][],cr[][],cs[][];

int l1[][],r1[][];

int max(int a,int b){return a>b?a:b;}

int C(int x){return x*(x+)/;}

int main(){

    scanf("%d%s",&k,s+);

    n=strlen(s+);

    for(int i=;i<=n;++i)if(s[i]!='G')s[i]=;

    for(int i=;i<=n;++i)if(s[i])cs[i][i]=cl[i][i]=cr[i][i]=;

    for(int d=;d<n;++d)for(int l=,r=+d;r<=n;++l,++r){

        if(s[r])cl[l][r]=cl[l][r-]+;

        if(s[l])cr[l][r]=cr[l+][r]+;

        cs[l][r]=max(max(cs[l][r-],cs[l+][r]),max(cl[l][r],cr[l][r]));

    }

    for(int i=;i<=n;++i){

        for(int j=;j<=i;++j)if(cs[j][i]>=k)++ls[i];

        for(int j=i;j<=n;++j)if(cs[i][j]>=k)++rs[i];

    }

    for(int i=n;i;--i)rs[i]+=rs[i+];

    for(int i=;i<n;++i)ans+=1ll*ls[i]*C(n-i)+1ll*rs[i+]*i-1ll*ls[i]*rs[i+];

    for(int i=;i<=n;++i)for(int j=i;j<=n;++j){

        if(cs[i][j]<k&&cs[i][j]){

            if(cl[i][j])++l1[j][cl[i][j]];

            if(cr[i][j])++r1[i][cr[i][j]];

        }

    }

    for(int i=n;i;--i)for(int j=;j<k;++j)r1[i][j]+=r1[i+][j];

    for(int i=;i<=n;++i)for(int j=k-;j;--j)r1[i][j]+=r1[i][j+];

    for(int i=;i<n;++i)for(int j=;j<k;++j)ans+=1ll*l1[i][j]*r1[i+][k-j];

    printf("%lld",ans);

    return ;

}

说明：字符串A和字符串B的+运算指将B连在A的后面，即A+B=AB,如“RRG”+“GBB”=“RRGGBB”。

例如：S="GRG",K=2,因为S中一共就2个'G',而要求K=2，所以只有1个四元组（0,0,2,2）成立，即"G"+"G"="GG".

Input

第一行一个整数K，1<=K<=3000.

第二行一个字符串S，1<=len（S）<=3000,且只由'R','G','B'三种字符组成。

Output

一个整数，即不同的四元组(a,b,c,d)的个数。

码农公寓

相关文章