题目：
在两个序列自动机上同时走，这样暴搜。
先走字典序小的字符，一边搜一边输出，就是按字典序排序的。
方案数很多，需要高精度？空间很小，要压位。1e9的20位恰好够。
不开 n*n 的DP数组，给出现的状态分配一个位置，开 3e6 的DP数组，空间就能了。
#include#include #include #define ll long longusing namespace std;const int N=3015,K=60;int n,m,c[N][K],d[N][K],lst[K];char a[N],b[N];int Id(char ch){ if(ch<='Z')return ch-'A'; return ch-'a'+26;}char Id2(int k){ if(k<26)return k+'A'; return k-26+'a';}namespace S1{ int ans,top; char s[N]; void dfs(int p0,int p1) { printf("%s\n",s+1); ans++; for(int i=0;i<52;i++) if(c[p0][i]<=n&&d[p1][i]<=m) { s[++top]=Id2(i); dfs(c[p0][i],d[p1][i]); s[top]=s[top+1];top--; } } void solve() {dfs(0,0); printf("%d\n",ans);}}namespace S2{ const int M=3e6,bs=1e9; int tot; int dy[N][N]; struct Node{ int a[20];// void Inc(int k) { a[1]+=k; for(int i=1;i<=a[0];i++) if(a[i]>=bs)a[i]-=bs,a[i+1]++; while(a[a[0]+1])a[0]++; } void Inc(Node k) { int lm=max(a[0],k.a[0]); for(int i=1;i<=lm;i++) { a[i]+=k.a[i]; if(a[i]>=bs)a[i+1]+=a[i]/bs,a[i]%=bs; } while(a[a[0]+1])a[0]++; } void print() { printf("%d",a[a[0]]); for(int i=a[0]-1;i;i--) printf("%09d",a[i]);puts(""); } }dp[M]; int dfs(int p0,int p1) { if(dy[p0][p1])return dy[p0][p1]; int cr=++tot; dy[p0][p1]=cr; dp[cr].Inc(1); for(int i=0,x,y;i<52;i++) if((x=c[p0][i])<=n&&(y=d[p1][i])<=m) { int v=dfs(x,y); dp[cr].Inc(dp[v]); } return cr; } void solve() { int v=dfs(0,0); dp[v].print();}}int main(){ scanf("%d%d",&n,&m); scanf("%s",a+1); scanf("%s",b+1); for(int i=0;i<52;i++)lst[i]=n+1; for(int i=n;i>=0;i--) { for(int j=0;j<52;j++) c[i][j]=lst[j]; lst[Id(a[i])]=i; } for(int i=0;i<52;i++)lst[i]=m+1; for(int i=m;i>=0;i--) { for(int j=0;j<52;j++) d[i][j]=lst[j]; lst[Id(b[i])]=i; } int op;scanf("%d",&op); if(op==1)S1::solve(); else S2::solve(); return 0;}