TJOI2018 Day1 T3

TJOI2018 Day1 T3

​​ 题意：给定一个串s lenth<=15 给一个n 再给一个字符集 问n长度的串中不出现noi 且n长度的串与s串的lcs为等级 求每个等级有多少个不同的n长度的串

题解：​​这个为基础

在原有的dp数组上再增加一维[0/1/2]分别表示当前串的末尾构成的noi的长度为多少了

然后枚举八种情况 分别转移即可

#include#include#includeusing namespace std;const int mod=1e9+7;int g[20],h[20],w[20],S,dp[2][33768][3],mp[3][3],trans[33768][3],bin[20],n,m,ans[20];char s1[20];inline int make(int *h){int s=0; for (int i=1;i<=n;++i){ s|=(h[i]-h[i-1])*bin[i-1]; }return s;}inline void make1(int *g,int s){g[0]=0; for (int i=1;i<=n;++i) g[i]=g[i-1],g[i]+=(s&bin[i-1])>0;}inline void pre(){ for (int owo=0;owo<3;++owo){ for (int s=0;s<=S;++s){ make1(g,s);memset(h,0,sizeof(h)); for (int i=1;i<=n;++i) h[i]=max(h[i-1],max(g[i],(w[owo]==s1[i])*(g[i-1]+1))); trans[s][owo]=make(h); } }}inline void inc(int &x,int v){x=x+v>=mod?x+v-mod:x+v;}inline int bc(int x){int tmp=0; for (int i=0;i<=n;++i) if (x&bin[i]) ++tmp;return tmp;}int main(){ freopen("party.in","r",stdin); freopen("party.out","w",stdout); scanf("%d%d",&m,&n);w[0]='N';w[1]='O';w[2]='I'; for (int i=0;i<=15;++i) bin[i]=1<

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