luogu 4608

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
const ll lim=1000000000000000000ll;
int nxt[3505][60][2];
int vis[3505][3505];
struct Bignum
{
    ll f[15];
    int ilen;
    friend Bignum operator  + (Bignum a,Bignum b)
    {
        Bignum ret;
        memset(ret.f,0,sizeof(ret.f));
        for(int i=1;i<=max(a.ilen,b.ilen);i++)
        {
            ret.f[i]+=a.f[i]+b.f[i];
            if(ret.f[i]>=lim)ret.f[i+1]+=ret.f[i]/lim,ret.f[i]%=lim;
        }
        ret.ilen=max(a.ilen,b.ilen);
        while(ret.f[ret.ilen]>=lim)ret.f[ret.ilen+1]+=ret.f[ret.ilen]/lim,ret.f[ret.ilen]%=lim,ret.ilen++;
        while(ret.f[ret.ilen+1])ret.ilen++;
        return ret;
    }
}dp[3105][3105];
char ret[3505];
int ttop=0;
void build(char *s,int ilen,int num)
{
    for(int i=ilen-1;i>=0;i--)
    {
        for(int j=1;j<=58;j++)nxt[i][j][num]=nxt[i+1][j][num];
        nxt[i][s[i+1]-‘A‘+1][num]=i+1;
    }
}
void dfs(int x,int y)
{
    printf("%s\n",ret+1);
    for(int i=1;i<=58;i++)
    {
        if(nxt[x][i][0]&&nxt[y][i][1])
        {
            ret[++ttop]=i+‘A‘-1;
            dfs(nxt[x][i][0],nxt[y][i][1]);
            ret[ttop]=‘ ‘;
            ttop--;
        }
    }
}
void redfs(int x,int y)
{
    if(vis[x][y])return;
    vis[x][y]=1;
    dp[x][y].ilen=dp[x][y].f[1]=1;
    for(int i=1;i<=58;i++)
    {
        if(nxt[x][i][0]&&nxt[y][i][1])
        {
            redfs(nxt[x][i][0],nxt[y][i][1]);
            dp[x][y]=dp[x][y]+dp[nxt[x][i][0]][nxt[y][i][1]];
        }
    }
}
ll n,m;
int typ;
char s1[1005],s2[1005];
int main()
{
    scanf("%lld%lld",&n,&m);
    scanf("%s%s",s1+1,s2+1);
    build(s1,n,0),build(s2,m,1);
    scanf("%d",&typ);
    if(typ)dfs(0,0);
    redfs(0,0);
    for(int i=dp[0][0].ilen;i>=1;i--)
    {
        if(i==dp[0][0].ilen)printf("%lld",dp[0][0].f[i]);
        else printf("%018lld",dp[0][0].f[i]);
    }
    return 0;
}