室内装修网站,如何设置网站子域名,天津住房与城乡建设厅网站,成都展示型网站开发传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的串sss#xff0c;其只包含NOINOINOI三个字母#xff0c;给你一个mmm#xff0c;代表ttt串的长度#xff0c;ttt串包含NOINOINOI三个字母但是不存在三个连续的NOINOINOI子串#xff…传送门 文章目录题意思路题意
给你一个长度为nnn的串sss其只包含NOINOINOI三个字母给你一个mmm代表ttt串的长度ttt串包含NOINOINOI三个字母但是不存在三个连续的NOINOINOI子串输出n1n1n1行第iii行输出有多少合法的ttt串与sss串的lcslcslcs为iii。
m≤1000,n≤15m\le1000,n\le15m≤1000,n≤15
思路
也是一个dpdpdp套dpdpdp的题但是多了一个限制就是不存在连续的NOINOINOI串这个我们只需要在最后转移的时候加一个状态代表当前连续串的长度是多少NONONO就是长度为222。转移的时候避免掉不合法状态转移对于状态机的构建与上一个题相同就不多说了。
复杂度O(3∗2∗m∗2n)O(3*2*m*2^n)O(3∗2∗m∗2n)
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N110,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N];
LL f[2][116][4],ans[N];
int ne[5][116];
int g1[N],g2[N];
char s[N];int get(char ch) {if(chN) return 1;if(chO) return 2;if(chI) return 3;while(1);return -1;
}void init() {memset(ne,0,sizeof(ne));for(int i0;i1n;i) {for(int j1;jn;j) g2[j]g2[j-1](i(j-1)1);for(int k1;k3;k) {for(int j1;jn;j) {g1[j]max(g1[j-1],g2[j]);if(a[j]k) g1[j]max(g1[j],g2[j-1]1);}int state0;for(int i0;in;i) if(g1[i1]-g1[i]) state1i;ne[k][i]state;}}
}void solve() {memset(f[0],0,sizeof(f[0]));memset(f[1],0,sizeof(f[1]));int now0;f[now][0][0]1; now^1;for(int i1;im;i,now^1) {memset(f[now],0,sizeof(f[now]));for(int len0;len2;len) {for(int k1;k3;k) {int to;if(len1k2) to2;else if(len2k3) continue;else if(k1) to1;else to0;for(int j0;j1n;j) {(f[now][ne[k][j]][to]f[now^1][j][len])%mod;}}}}now^1;for(int i0;in;i) ans[i]0;for(int i0;i1n;i) {for(int j0;j2;j) {(ans[__builtin_popcount(i)]f[now][i][j])%mod;}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d%s,m,n,s1); for(int i1;in;i) a[i]get(s[i]);init(); solve();for(int i0;in;i) printf(%lld\n,ans[i]%mod);return 0;
}
/**/
