NC218457 九峰与子序列（dfs）

40有点大，我们考虑折半查找

这样每个字符串有取和不取两种可能

之后乘法原理即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=5e6+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int base=131;
string a[50];
int len[50];
ll p[N];
string s;
ll cnt1[N],cnt2[N];
ll h[N],d[N];
int m;
void init(){
    int i;
    p[0]=1;
    for(i=1;i<(int)s.size();i++){
        p[i]=p[i-1]*base%mod;
    }
    for(i=1;i<s.size();i++){
        h[i]=(h[i-1]*base+s[i]-'a')%mod;
    }
}
ll cal(string t){
    int i;
    ll tmp=0;
    for(i=0;i<t.size();i++){
        tmp=(tmp*base+t[i]-'a')%mod;
    }
    return tmp;
}
ll get(int l,int r){
    ll tmp=0;
    tmp=(h[r]-h[l-1]*p[r-l+1])%mod;
    tmp=(tmp+mod)%mod;
    return tmp;
}
void dfs1(int u,int x){
    cnt1[x-1]++;
    if(u==m+1)
        return ;
    for(int i=u;i<=m;i++){
        if(d[i]==get(x,x+len[i]-1)){
            dfs1(i+1,x+len[i]);
        }
    }
}
void dfs2(int u,int x){
    cnt2[x+1]++;
    if(u<=m)
        return ;
    for(int i=u;i>m;i--){
        if(d[i]==get(x-len[i]+1,x)){
            dfs2(i-1,x-len[i]);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int i;
    cin>>s;
    s=" "+s;
    init();
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++){
        d[i]=cal(a[i]);
        len[i]=(int)a[i].size();
    }
    m=n/2;
    dfs1(1,1);
    dfs2(n,s.size()-1);
    ll ans=0;
    for(i=1;i<(int)s.size()-1;i++){
        ans+=(cnt1[i]*cnt2[i+1]);
    }
    ans+=cnt2[1]+cnt1[(int)s.size()-1];
    cout<<ans<<endl;
    return 0;
}