CodeForces - 1051E ：Vasya and Big Integers（Z算法 & DP ）

题意：给定字符串S，A，B。现在让你对S进行切割，使得每个切割出来的部分在[A,B]范围内，问方案数。

思路：有方程，dp[i]=Σ dp[j] (S[j+1,i]在合法范围内)。假设M和N的最长公共前缀为长度是LCP，那么字符串M>=字符串N的条件是 LCP=|N|或者(LCP<|N|&&M[lcp+1]>N[lca+1])；小于同理。求出范围就可以用前缀和 O（N）求DP了。

而LCP显然可以用exkmp求。最近发现Z算法比较好写。尝试了一下。这里把两个串连起来一次性求，看起来比较舒服。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int Mod=;

char s[maxn<<],l[maxn],r[maxn];

int z1[maxn],z2[maxn],lena,lenl,lenr;

void Z(char a[],char t[],int z[])

{

    int f=strlen(a+),w=strlen(t+);

    a[f+]='&'; rep(i,,w) a[f++i]=t[i]; int n=f+w+;

    z[]=n; int L=,R=;

    rep(i,,n) {

        if(R<i) z[i]=;

        else z[i]=min(R-i+,z[i-L+]);

        while(i+z[i]<=n&&a[i+z[i]]==a[z[i]+]) z[i]++;

        if(i+z[i]->R) L=i,R=i+z[i]-;

    }

    rep(i,,w) z[i]=z[f++i];

}

int dp[maxn],sum[maxn];

int main()

{

    scanf("%s%s%s",s+,l+,r+);

    lena=strlen(s+); lenl=strlen(l+); lenr=strlen(r+);

    Z(l,s,z1); Z(r,s,z2);

    dp[lena+]=sum[lena+]=;

    for(int i=lena;i>=;i--) {

        sum[i]=sum[i+];

        if(s[i]=='') dp[i]=(l[]=='')*dp[i+],sum[i]=(sum[i]+dp[i])%Mod;

        else {

            int L=i+lenl,R=min(i+lenr-,lena);

            if(z1[i]==lenl||s[i+z1[i]]>l[z1[i]+]) L--;

            if(R<lena&&(z2[i]==lenr||s[i+z2[i]]<r[z2[i]+])) R++;

            if(L<=R) dp[i]=(sum[L+]-sum[R+]+Mod)%Mod,sum[i]=(sum[i]+dp[i])%Mod;

        }

    }

    printf("%d\n",dp[]);

    return ;
}

巴特西

CodeForces - 1051E ：Vasya and Big Integers（Z算法 & DP ）

最新文章

热门文章