P4591

· · 题解

这这这不是 DP 吗？

题目大意：一个蛋白质，由 k 个氨基酸组成，第 i 个氨基酸有 a_i 种可能性，对于每种蛋白质可能，ans 加上蛋白质在他给出的碱基串中出现的次数。

用 dp_{i,j} 表示第 i 个氨基酸选完后，完成前 j 个碱基有几种可能性（由于没有说从必须到开头或结尾，所以 dp_{0,j} 需要赋初值为 1，0<=j<=s.size()）。

判断是否相等可以用hash维护，时间复杂度为 O(\sum _ {i = 1} ^ k a_i \times k \times (n+m))。

最后输出 \sum _ {i =1} ^ n dp_{k,i} 即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define Mod (1000000007)
#define q (27)

using namespace std;

ll ned[10005]={1};
ll n, a, m, k, len;
string s;
ll hsh[10005], tmp, dp[105][10005], sum=0;

int main()
{
    cin>>k>>s;
    n=s.size();
    for(ll i=0;i<=n;i++){
        dp[0][i]=1;
    }
    for(ll i=0;i<n;i++){
        hsh[i+1]=(hsh[i]*q+s[i])%Mod;
        ned[i+1]=ned[i]*q%Mod;
    }
    for(ll i=1;i<=k;i++){
        cin>>a;
        for(int null_help=1;null_help<=a;null_help++){
            cin>>s;
            len=s.size(), tmp=0;
            for(ll j=0;j<len;j++){
                tmp=(tmp*q+s[j])%Mod;
            }

            for(ll l=0, r=len;r<=n;l++, r++){
                if(((hsh[r]-hsh[l]*ned[len]%Mod)%Mod+Mod)%Mod!=tmp) continue;
                dp[i][r]=(dp[i][r]+dp[i-1][l])%Mod;
            }
        }
    }

    for(ll i=1;i<=n;i++){
        sum=(sum+dp[k][i])%Mod;
    }

    cout<<sum;
    return 0;
}