题解：P8643 [蓝桥杯 2016 国 AC] 碱基

· · 题解

看到题解里有很多都是爆搜的，但是这并没有什么技术含量。这里我发一个 DP 题解。

题目

这个题面写的很绕，但其实就想表达：有多少个连续子串满足长度为 k，并且有 m 个字符串都包括此子串。

解法

哈希必不可少，运用前缀和的方法（可参照这题）算出每个字符串中长度为 k 的不同连续子串的数量 p_{i,tot_i}，以及每种连续字串的个数 cnt_{i,H}。

接下来便是 DP 环节。f_{i,j,H} 表示以 i 为结尾（必选 i），选了 j 个，哈希值为 H 的子串的选择方案有多少种。

第一重循环当然是遍历字符串，下一重就是遍历此字符串中长度为 k 的子串的哈希值 H（前面处理过），初始值 f_{i,1,H}\gets cnt_{i,H}。接着遍历选的个数（最大值为 m），最后一重循环遍历 lst，范围为 1\le lst<i。

DP 的方法即为把所有的 lst 的方案数乘 cnt_{i,H} 后加起来，也就是：

f_{i,j,H}=\sum _ {lst = 1} ^ {i-1} f_{lst,j-1,H}\times cnt_{i,H}

最后把所有的 f_{i,m,H} 加起来（可以在 DP 中 j 的循环内操作）即为答案。

设所有长度为 k 的哈希最大值（自然溢出后）为 H， 则时间复杂度为 O(n^2m\log H)。

注意取模！

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e5+5,base=131,mod=1e9+7;
int n,m,k;
ll ans;
ull pre[N],h[10][N],p[10][N],tot[10];
string s;
map<ull,ll>cnt[10],f[10][10];//f[i][j][H]表示前i个串（以i为结尾），选了j个，哈希值为H的数量 
map<ull,bool>vis;
ull Hash(int l,int r,int i){
    return h[i][r]-h[i][l-1]*pre[r-l+1];
    //123456789 4567->1234567-123*10^4
}
int main(){
    cin>>n>>m>>k; 
    pre[0]=1;
    for(int i=1;i<=1e5;i++) pre[i]=pre[i-1]*base;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=s.size();j++) h[i][j]=h[i][j-1]*base+(s[j-1]-'A'+1);
        vis.clear();
        for(int j=1;j+k-1<=s.size();j++){
            ull H=Hash(j,j+k-1,i);
            cnt[i][H]++;
            if(!vis[H]){
                p[i][++tot[i]]=H;
                vis[H]=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int q=1;q<=tot[i];q++){
            ull H=p[i][q];
            f[i][1][H]=cnt[i][H];
            for(int j=1;j<=m;j++){
                for(int lst=1;lst<i;lst++){
                    f[i][j][H]=(f[i][j][H]+f[lst][j-1][H]*cnt[i][H]%mod)%mod;
                }
                if(j==m) ans=(ans+f[i][j][H])%mod;
            }
        }
    }
    cout<<ans;
    return 0;
}