题目链接

洛谷P4608

题解

建个序列自动机后

第一问暴搜

第二问dp + 高精

设\(f[i][j]\)为两个序列自动机分别走到\(i\)和\(j\)节点的方案数，答案就是\(f[0][0]\)

由于空间卡的很紧，高精不仅要压位，还要动态开内存

由于有些状态是没用的，记忆化搜索以减少内存损失

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 3015,P = 1000000000,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

char X[maxn],Y[maxn];

int typ,n,m,last[60];

inline int id(char c){return c >= 'a' ? 26 + c - 'a' : c - 'A';}

struct LAM{

	int ch[maxn][52],cnt;

	void build(char* S,int len){

		for (int i = 0; i < 52; i++) last[i] = 0;

		cnt = len;

		for (int i = len; i; i--){

			for (int j = 0; j < 52; j++)

				ch[i][j] = last[j];

			last[id(S[i])] = i;

		}

		for (int i = 0; i < 52; i++) ch[0][i] = last[i];

	}

}A,B;

char s[maxn];

int len,ans;

void dfs(int u,int v){

	ans++;

	for (int i = 1; i <= len; i++) putchar(s[i]); puts("");

	for (int i = 0; i < 52; i++)

		if (A.ch[u][i] && B.ch[v][i]){

			s[++len] = i > 25 ? 'a' + i - 26 : 'A' + i;

			dfs(A.ch[u][i],B.ch[v][i]);

			len--;

		}

}

void work1(){

	dfs(0,0);

	printf("%d\n",ans);

};

struct NUM{

	int len;

	LL* s;

	void init(){

		s = new LL[20];

		for (int i = 0; i < 20; i++) s[i] = 0;

		len = 0;

	}

	void out(){

		if (!len){puts("0"); return;}

		printf("%lld",s[len - 1]);

		for (int i = len - 2; ~i; i--)

			printf("%09lld",s[i]);

	}

	void add(const NUM& a){

		LL carry = 0,tmp,L = max(len,a.len);

		for (int i = 0; i < L; i++){

			tmp = s[i] + a.s[i] + carry;

			s[i] = tmp % P;

			carry = tmp / P;

		}

		if (carry) s[L] += carry;

		len = 0;

		for (int i = 19; ~i; i--) if (s[i]){len = i + 1; break;}

	}

}f[maxn][maxn];

int vis[maxn][maxn];

void DFS(int u,int v){

	if (vis[u][v]) return;

	vis[u][v] = true;

	f[u][v].init();

	f[u][v].s[0] = f[u][v].len = 1;

	for (int i = 0; i < 52; i++)

		if (A.ch[u][i] && B.ch[v][i]){

			DFS(A.ch[u][i],B.ch[v][i]);

			f[u][v].add(f[A.ch[u][i]][B.ch[v][i]]);

		}

}

void work2(){

	DFS(0,0);

	f[0][0].out();

}

int main(){

	n = read(); m = read();

	scanf("%s%s%d",X + 1,Y + 1,&typ);

	A.build(X,n); B.build(Y,m);

	if (typ) work1();

	else work2();

	return 0;

}