对外网站建设情况汇报,开发电子商务网站,企业培训课程有哪些内容,工信部网站 备案时间正题
题目链接:https://www.luogu.com.cn/problem/P4590 题目大意
给出一个长度为mmm的字符串sss。 对于每个k∈[0,m]k\in[0,m]k∈[0,m]求有多少个长度为nnn的字符串满足与sss的最长公共子序列长度为kkk且不包含NOINOINOI这一个子串。 可用字符集是{N,O,I}\{N,O,I\}{N,O,I} 解…正题
题目链接:https://www.luogu.com.cn/problem/P4590 题目大意
给出一个长度为mmm的字符串sss。 对于每个k∈[0,m]k\in[0,m]k∈[0,m]求有多少个长度为nnn的字符串满足与sss的最长公共子序列长度为kkk且不包含NOINOINOI这一个子串。 可用字符集是{N,O,I}\{N,O,I\}{N,O,I} 解题思路
显然这个NOINOINOI的限制是很无聊的先不管。
然后就是求最长公共子序列恰好为kkk之前翻资料的时候看到过这题然后mmm又只有151515所以可以直接dpdpdp套dpdpdp。
先考虑正常dpdpdp求最长公共子序列就是设gi,jg_{i,j}gi,j表示第一个串匹配到iii第二个串匹配到jjj时的长度。那么显然对于一个iii来说是可以对应多个jjj的。 然后我们要在转移dpdpdp的自动机上对于iii维护每个gi,jg_{i,j}gi,j
虽然mmm很小但是这个状态还是很多要加点优化。挖掘一下ggg数组的性质发现其实有gi,j−1≤gi,j≤gi,j−11g_{i,j-1}\leq g_{i,j}\leq g_{i,j-1}1gi,j−1≤gi,j≤gi,j−11。所以可以状压一下用111表示这里加了111000表示没有加一就可以表示出所有的状态了。
然后先预处理出每个状态加某个字符之后会转移到哪个状态nxts,cnxt_{s,c}nxts,c然后设fi,sf_{i,s}fi,s表示现在已经有iii个字符dpdpdp数组状态为jjj时的方案数然后转移就好了。
之后NOINOINOI那个限制多开一维来维护就好了要滚动不然会炸。
时间复杂度O(2mn)O(2^mn)O(2mn)然后因为要判NOINOINOI所以常数比较大。 code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1100,M16,P1e97;
const int d[3][3]{{1,0,0},{1,2,0},{1,0,3}};
int n,m,f[3][1M][3] ,ans[M];
int a[M],g[1M],h[1M],nxt[1M][3];
char s[M];
int ct(int x){int ans0;while(x)x-(x-x),ans;return ans;
}
int main()
{scanf(%d%d,n,m);scanf(%s,s1);for(int i1;im;i){if(s[i]O)a[i]1;if(s[i]I)a[i]2;}int MS(1m);for(int s0;sMS;s){for(int i1;im;i)g[i]g[i-1]((si-1)1);for(int c0;c3;c){for(int i1;im;i){h[i]max(h[i-1],g[i]);if(a[i]c)h[i]max(h[i],g[i-1]1);if(h[i]h[i-1])nxt[s][c]|(1i-1);}}}f[0][0][0]1;for(int i1;in;i){memset(f[i1],0,sizeof(f[i1]));for(int s0;sMS;s){for(int t0;t3;t){for(int c0;c3;c){if(t2c2)continue;int zd[t][c];(f[i1][nxt[s][c]][z]f[~i1][s][t])%P;}}}}for(int s0;sMS;s)for(int t0;t3;t)(ans[ct(s)]f[n1][s][t])%P;for(int i0;im;i)printf(%d\n,ans[i]);return 0;
}
