自动搬运

查看原文

来自洛谷，原作者为

	billtun 我 can 说 Chenglish 特别 well.

搬运于2025-08-24 22:01:44，当前版本为作者最后更新于2023-08-24 17:03:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这这这不是 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;
}