TJOI2018 Day2 T1

TJOI2018 Day2 T1

​​ 题意：给定k种类型 每种类型里有一定数量的串

求给定串中 k种类型按照顺序出现的方案数 只要位置不同或者在这个类型里属于不同的两种串即算不同答案

hash预处理 dp[i][j]表示当前在待匹配串的i位置 我现在属于第j种串的结尾我的总答案是多少

1e7枚举状态转移即可

#include#include#include#define ll unsigned long long#define lle long longusing namespace std;const int g1=1000003;const int g2=100003;const int N=10010;const int mod=1000000007;ll p1[N],p2[N],hs1[N],hs2[N],hst1[110][11],hst2[110][11];char s[N],s1[N];int nm[110],len[110][11],k;lle dp[N][110];inline bool judge(int l,int r,int kd,int d){ ll tmp1,tmp2; tmp1=hs1[r]-hs1[l]*p1[r-l];tmp2=hs2[r]-hs2[l]*p2[r-l]; return (tmp1==hst1[kd][d])&&(tmp2==hst2[kd][d]);}int main(){ freopen("str.in","r",stdin); freopen("str.out","w",stdout); scanf("%d",&k);scanf("%s",s+1); int n=strlen(s+1);p1[0]=1;p2[0]=1; for (int i=1;i<=n;++i) p1[i]=p1[i-1]*g1,p2[i]=p2[i-1]*g2, hs1[i]=hs1[i-1]*g1+s[i],hs2[i]=hs2[i-1]*g2+s[i]; for (int owo=1;owo<=k;++owo){ int kd;scanf("%d",&kd);nm[owo]=kd; for (int j=1;j<=kd;++j){ scanf("%s",s1+1);static ll tmp1,tmp2;tmp1=tmp2=0; int le=strlen(s1+1);len[owo][j]=le; for (int i=1;i<=le;++i){ tmp1=tmp1*g1+s1[i]; tmp2=tmp2*g2+s1[i]; }hst1[owo][j]=tmp1;hst2[owo][j]=tmp2; } }for (int i=0;i<=n;++i) dp[i][0]=1; for (int i=1;i<=n;++i){ for (int kd=1;kd<=k;++kd){int tmp=0; for (int j=1;j<=nm[kd];++j){ if (i-len[kd][j]<0) continue; if (judge(i-len[kd][j],i,kd,j)) tmp+=dp[i-len[kd][j]][kd-1];tmp%=mod; }dp[i][kd]=tmp; } }lle ans=0; for (int i=1;i<=n;++i) ans+=dp[i][k],ans%=mod; printf("%lld\n",ans); return 0;

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。