Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,l,A[33],B[33],c[33],d[33],pre[33],f[33][33][33];
string a[6],b[6];

void calcPre(int A[],int c[])
{
    int i=1,j=0;
    while (i<=l)
    {
        while (j && A[i]!=A[j]) j=pre[j];
        c[i]=j; j++; i++;
        if (i>l || A[i]!=A[j]) pre[i]=j;
        else pre[i]=pre[j];
    }
}

int main()
{
    cin >> n >> l;

    for (int i=1;i<=5;i++) cin >> a[i];
    for (int i=1;i<=l;i++)
        for (int j=1;j<=5;j++)
            A[i]+=(a[j][i-1]=='#')*(1<<(j-1));

    for (int i=1;i<=5;i++) cin >> b[i];
    for (int i=1;i<=l;i++)
        for (int j=1;j<=5;j++)
            B[i]+=(b[j][i-1]=='#')*(1<<(j-1));

    calcPre(A,c);
    calcPre(B,d);

    f[0][0][0]=1;
    for (int i=1;i<=n;i++)
        for (int x=0;x<32;x++)
            for (int j=0;j<=l;j++)
            {
                int jj=j;
                if (j<l)
                {
                    while (jj && A[jj+1]!=x) jj=c[jj];
                    if (A[jj+1]==x) jj++;
                }
                for (int k=0;k<=l;k++)
                {
                    int kk=k;
                    if (k<l)
                    {
                        while (kk && B[kk+1]!=x) kk=d[kk];
                        if (B[kk+1]==x) kk++;
                    }
                    f[i][jj][kk]+=f[i-1][j][k];
                    f[i][jj][kk]%=1000000;
                }
            }
    int re=0;
    for (int j=0;j<l;j++) re=(re+f[n][j][l])%1000000;
    for (int k=0;k<l;k++) re=(re+f[n][l][k])%1000000;
    cout << re << endl;
}

Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
#include<cassert>
#include<cstdio>
using namespace std;

const int N = 30, MOD = 1e6;
int pa[N], pb[N], na[N], nb[N], n, len;

void getPattern(int a[]) {
    string s[5];
    for(int i = 0; i < 5; ++i) cin >> s[i];
    for(int i = 0; i < len; ++i) {
        a[i] = 0;
        for(int j = 0; j < 5; ++j)
            if(s[j][i] == '#') a[i] |= 1 << j;
    }
}

void enter() {
    cin >> n >> len;
    getPattern(pa);
    getPattern(pb);
}

void buildFailure(int a[], int next[]) {
    next[0] = -1;
    for(int i = 1, j = -1; i < len; ++i) {
        while(j >= 0 && a[i] != a[j + 1]) j = next[j];
        if(a[i] == a[j + 1]) ++j;
        next[i] = j;
    }
}

int f[N + 1][N + 1][N + 1][2];

int dp(int a[], int b[], int na[], int nb[]) {
    memset(f, 0, sizeof f);
    f[0][0][0][0] = 1;
    int res = 0;
    for(int i = 0; i <= n; ++i)
        for(int ma = 0; ma <= len; ++ma)
            for(int mb = 0; mb < len; ++mb)
                for(int c = 0; c < 2; ++c) if(f[i][ma][mb][c] > 0) {
                    if(i == n) {
                        if(c == 1) (res += f[i][ma][mb][c]) %= MOD;
                    } else {
                        for(int mask = 0; mask < 32; ++mask) {
                            int tma = ma - 1, tmb = mb - 1;
                            if(tma == len - 1) tma = na[tma];
                            while(tma >= 0 && a[tma + 1] != mask) tma = na[tma];
                            if(a[tma + 1] == mask) ++tma;
                            while(tmb >= 0 && b[tmb + 1] != mask) tmb = nb[tmb];
                            if(b[tmb + 1] == mask) ++tmb;
                            (f[i + 1][tma + 1][tmb + 1][c | (tma == len - 1 ? 1 : 0)] += f[i][ma][mb][c]) %= MOD;
                        }
                    }
                }
    return res;
}

int main() {
#ifdef __DNK__
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    enter();
    buildFailure(pa, na);
    buildFailure(pb, nb);
    cout << (dp(pa, pb, na, nb) + dp(pb, pa, nb, na)) % MOD;
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 33;
const int MOD = 1000000;

using namespace std;

int n, L;

int getMask(char a[]) {
  int ret = 0;
  FOR(i, 0, 5)
  if (a[i] == '#')
    ret |= 1 << i;
  return ret;
}

void buildMask(char a[], int mask) {
  FOR(i, 0, 5)
  if (mask & (1 << i))
    a[i] = '#';
  else
    a[i] = '.';
}

void makeLove(char a[][5], int fail[][N]) {
  int kmp[N];
  kmp[0] = 0;
  FOR(i, 1, L)  {
    int j = kmp[i - 1];
    while (j && !equal(a[i], a[i] + 5, a[j])) j = kmp[j - 1];
    kmp[i] = j + equal(a[i], a[i] + 5, a[j]);
    //if (kmp[i]) cerr << i << ' ' << kmp[i] << endl;
  }
  RESET(fail, 0);
  fail[0][getMask(a[0])] = 1;
  FOR(matched, 1, L) FOR(mask, 0, 32) {
    char tmp[5];
    buildMask(tmp, mask);
    int j = matched;
    while (j && !equal(a[j], a[j] + 5, tmp)) j = kmp[j - 1];
    fail[matched][mask] = j + (equal(a[j], a[j] + 5, tmp));
    /*
    if (fail[matched][mask]) {
      cerr << "fail " << matched << ' ' << mask << ' ' << fail[matched][mask] << endl;
    }
    */
  }
  FOR(mask, 0, 32) fail[L][mask] = L;
}

void add(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int f[N][N][N]; //* pos, matchedA, matchedB
int fail[2][N][N];
char a[2][N][5];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("XYZ.inp", "r", stdin);
  #endif // _LAD_
  cin >> n >> L;
  FOR(t, 0, 2) {
    FOR(i, 0, 5) FOR(j, 0, L)
      cin >> a[t][j][i];
    /*
    FOR(i, 0, L) {
      FOR(j, 0, 5) cout << a[t][i][j];
      cout << endl;
    }
    cout << endl;
    */
    makeLove(a[t], fail[t]);
  }
  f[0][0][0] = 1;
  FOR(i, 0, n) FOR(more, 0, 32) {
    REP(matchA, 0, L) REP(matchB, 0, L)
    if (f[i][matchA][matchB])
      add(f[i + 1][fail[0][matchA][more]][fail[1][matchB][more]], f[i][matchA][matchB]);
  }
  int ans = 0;
  FOR(i, 0, L) {
    add(ans, f[n][L][i]);
    add(ans, f[n][i][L]);
  }
  cout << ans << endl;
  return 0;
}

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=31;
  oo=1000000;
var
  f1,f2:text;
  l,n:longint;
  d1,d2:array[0..MAXN,0..MAXN,0..MAXN,0..1] of longint;
  a,b:array[1..5,1..30] of longint;
  p1,p2:array[0..30] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,j:longint;
  ch:char;
begin
  readln(f1,n,l);
  for i:=1 to 5 do
    begin
      for j:=1 to l do
        begin
          read(f1,ch);
          if ch='.' then a[i,j]:=0 else a[i,j]:=1;
        end;
      readln(f1);
    end;
  for i:=1 to 5 do
    begin
      for j:=1 to l do
        begin
          read(f1,ch);
          if ch='.' then b[i,j]:=0 else b[i,j]:=1;
        end;
      readln(f1);
    end;
end;
function check1(ll,v1,v2,v3,v4,v5:longint):boolean;
begin
  check1:=false;
  if ll>l then exit;
  if ll<=0 then exit(true);
  if v1<>a[1,ll] then exit;
  if v2<>a[2,ll] then exit;
  if v3<>a[3,ll] then exit;
  if v4<>a[4,ll] then exit;
  if v5<>a[5,ll] then exit;
  check1:=true;
end;
function check2(ll,v1,v2,v3,v4,v5:longint):boolean;
begin
  check2:=false;
  if ll>l then exit;
  if ll<=0 then exit(true);
  if v1<>b[1,ll] then exit;
  if v2<>b[2,ll] then exit;
  if v3<>b[3,ll] then exit;
  if v4<>b[4,ll] then exit;
  if v5<>b[5,ll] then exit;
  check2:=true;
end;
procedure solve;
var
  i,l1,l2,k,ll1,ll2,kk:longint;
  v1,v2,v3,v4,v5:longint;
begin
  d1[0,0,0,0]:=1; d2[0,0,0,0]:=1;
  for i:=0 to n-1 do
  for l1:=0 to l do
  for l2:=0 to l-1 do
  for k:=0 to 1 do
    if d1[i,l1,l2,k]>0 then
    for v1:=0 to 1 do
    for v2:=0 to 1 do
    for v3:=0 to 1 do
    for v4:=0 to 1 do
    for v5:=0 to 1 do
      begin
        if (i=1) and (l1=1) and (l2=0) and (k=0)
        and (v1+v3+v4+v5=0) and (v2=1) then
          write('');
        if check1(l1+1,v1,v2,v3,v4,v5) then ll1:=l1+1
        else
          begin
            ll1:=l1;
            while not check1(ll1+1,v1,v2,v3,v4,v5) do
              ll1:=p1[ll1];
            inc(ll1);
          end;
        if check2(l2+1,v1,v2,v3,v4,v5) then ll2:=l2+1
        else
          begin
            ll2:=l2;
            while not check2(ll2+1,v1,v2,v3,v4,v5) do
              ll2:=p2[ll2];
            inc(ll2);
          end;
        if ll1=l then kk:=1 else kk:=k;
        if ll2<l then
          begin
            d1[i+1,ll1,ll2,kk]+=d1[i,l1,l2,k];
            if d1[i+1,ll1,ll2,kk]>oo then d1[i+1,ll1,ll2,kk]-=oo;
          end;
      end;
  for i:=0 to n-1 do
  for l1:=0 to l-1 do
  for l2:=0 to l do
  for k:=0 to 1 do
    if d2[i,l1,l2,k]>0 then
    for v1:=0 to 1 do
    for v2:=0 to 1 do
    for v3:=0 to 1 do
    for v4:=0 to 1 do
    for v5:=0 to 1 do
      begin
        if check1(l1+1,v1,v2,v3,v4,v5) then ll1:=l1+1
        else
          begin
            ll1:=l1;
            while not check1(ll1+1,v1,v2,v3,v4,v5) do
              ll1:=p1[ll1];
            inc(ll1);
          end;
        if check2(l2+1,v1,v2,v3,v4,v5) then ll2:=l2+1
        else
          begin
            ll2:=l2;
            while not check2(ll2+1,v1,v2,v3,v4,v5) do
              ll2:=p2[ll2];
            inc(ll2);
          end;
        if ll2=l then kk:=1 else kk:=k;
        if ll1<l then
          begin
            d2[i+1,ll1,ll2,kk]+=d2[i,l1,l2,k];
            if d2[i+1,ll1,ll2,kk]>oo then d2[i+1,ll1,ll2,kk]-=oo;
          end;
      end;
end;
procedure ans;
var
  l1,l2,k,sum:longint;
begin
  sum:=0;
  for l1:=0 to l do
  for l2:=0 to l do
  for k:=1 to 1 do
    begin
      sum+=d1[n,l1,l2,k]; if sum>oo then sum-=oo;
      sum+=d2[n,l1,l2,k]; if sum>oo then sum-=oo;
    end;
  writeln(f2,sum mod oo);
end;
function kt1(l1,r1,l2,r2:longint):boolean;
var
  i1,i2,h:longint;
begin
  kt1:=false;
  for i1:=l1 to r1 do
  for i2:=l2 to r2 do
    for h:=1 to 5 do
      if a[h,i1]<>a[h,i2] then exit;
  kt1:=true;
end;
function kt2(l1,r1,l2,r2:longint):boolean;
var
  i1,i2,h:longint;
begin
  kt2:=false;
  for i1:=l1 to r1 do
  for i2:=l2 to r2 do
    for h:=1 to 5 do
      if b[h,i1]<>b[h,i2] then exit;
  kt2:=true;
end;
procedure init;
var
  i,j:longint;
begin
  p1[1]:=0; p1[0]:=-1;
  for i:=2 to l do
    for j:=i-1 downto 1 do
      if kt1(1,j,i-j+1,i) then
        begin
          p1[i]:=j;
          break;
        end;
  p2[1]:=0; p2[0]:=-1;
  for i:=2 to l do
    for j:=i-1 downto 1 do
      if kt2(1,j,i-j+1,i) then
        begin
          p2[i]:=j;
          break;
        end;
end;
begin
  openF;
  inp;
  init;
  solve;
  ans;
  closeF;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   44
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define MASK(i) (1<<(i))
const int mod=(int)1e6;
const int m=5;
int s[MAX],t[MAX];
int n,len;
int f[MAX][MAX][MAX][2][2];
int kmpS[MAX],kmpT[MAX];
int nextS[MAX][MAX],nextT[MAX][MAX];
void add(int &x,const int &y) {
    x+=y;
    if (x>=mod) x-=mod;
}
void init(void) {
    char inp[MAX][MAX];
    scanf("%d%d",&n,&len);
    REP(i,m) scanf("%s",inp[i]+1);
    FOR(i,1,len) {
        int mask=0;
        REP(j,m) if (inp[j][i]=='#') mask|=MASK(j);
        s[i]=mask;
    }
    REP(i,m) scanf("%s",inp[i]+1);
    FOR(i,1,len) {
        int mask=0;
        REP(j,m) if (inp[j][i]=='#') mask|=MASK(j);
        t[i]=mask;
    }
}
void KMP(int s[],int kmp[],int next[][MAX]) {
    int j=kmp[1]=0;
    FOR(i,2,len) {
        while (j>0 && s[j+1]!=s[i]) j=kmp[j];
        if (s[j+1]==s[i]) j++;
        kmp[i]=j;
    }
    FOR(i,0,len) REP(k,MASK(m)) {
        int j=i;
        while (j>0 && (j>=len || s[j+1]!=k)) j=kmp[j];
        if (j<len && s[j+1]==k) j++;
        next[i][k]=j;
    }
}
void process(void) {
    KMP(s,kmpS,nextS);
    KMP(t,kmpT,nextT);
    f[0][0][0][0][0]=1;
    REP(i,n) REP(preS,len+1) REP(preT,len+1) REP(s,2) REP(t,2) if (f[i][preS][preT][s][t]>0)
        REP(chs,MASK(m)) {
            int ls=nextS[preS][chs];
            int lt=nextT[preT][chs];
            add(f[i+1][ls][lt][s||(ls==len)][t||(lt==len)],f[i][preS][preT][s][t]);
        }
    int res=0;
    REP(i,len+1) REP(j,len+1) {
        add(res,f[n][i][j][0][1]);
        add(res,f[n][i][j][1][0]);
    }
    printf("%d\n",res);
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int N, L;
int F[33][33][33];
int a[33], b[33];
int na[33][33], nb[33][33];

void init(int na[33][33], int a[33]) {
    for(int len=0;len<L;++len)
        for(int ad=0;ad<32;++ad)
            for(int r=0;r<=len+1;++r) {
                bool ok = true;
                for(int j=0;j<r;++j) if((j+1==r && a[j]!=ad) || (j+1<r && a[j]!=a[len-r+1+j])) ok = false;
                if(ok) na[len][ad] = r;
            }
    for(int ad=0;ad<32;++ad) na[L][ad] = L;
}

int main() {
    char c;
    cin >> N >> L;
    for(int i=0;i<5;++i)
        for(int j=0;j<L;++j)
            if(cin >> c, c=='#') a[j] = a[j] * 2 + 1;
            else a[j] = a[j] * 2;
    for(int i=0;i<5;++i)
        for(int j=0;j<L;++j)
            if(cin >> c, c=='#') b[j] = b[j] * 2 + 1;
            else b[j] = b[j] * 2;
    init( na, a);
    init( nb, b);
    F[0][0][0] = 1;
    for(int i=0;i<N;++i)
        for(int j=0;j<=L;++j)
            for(int k=0;k<=L;++k) 
                for(int ad=0;ad<32;++ad)
                    F[i+1][na[j][ad]][nb[k][ad]] = (F[i+1][na[j][ad]][nb[k][ad]] + F[i][j][k]) % 1000000;
    int res = 0;
    for(int i=0;i<=L;++i)
        for(int j=0;j<=L;++j)
            if((i==L) ^ (j==L)) res = (res + F[N][i][j]) % 1000000;
    printf("%d\n", res);
    return 0;
}