按照四个字符的个数分出点，连出一个图，缩点后用拓扑序求一个最长链。 忽略这个奇怪的组合数。
#include<bits/stdc++.h> using namespace std; const int maxn=32,maxm=55,N=maxn*maxn*maxn*maxn; typedef long long ll; queue<int> Q; int P[10]={2,3,5,7,11,13,17,19,23,29}; int n,m,len,trans[maxm][4],cost[maxm][4];char s[maxn]; struct NUM{ int num[10]; NUM(){memset(num,0,sizeof num);} friend inline NUM operator*(const NUM &a,const NUM &b){ NUM ret; for(int i=0;i<10;++i) ret.num[i]=a.num[i]+b.num[i]; return ret; } friend inline NUM operator/(const NUM &a,const NUM &b){ NUM ret; for(int i=0;i<10;++i) ret.num[i]=a.num[i]-b.num[i]; return ret; } inline ll getval(ll ret=1){ for(int i=0;i<10;++i) for(int j=1;j<=num[i];++j) ret*=P[i]; return ret; } }fac[maxn]; int Head[N],Next[N],V[N],cnt=0;ll val[N],ans=0; int dfn[N],low[N],st[N],ins[N],tot=0,top=0; int belong[N],in[N],num;ll siz[N],dis[N]; inline void add(int u,int v){Next[++cnt]=Head[u],V[cnt]=v,Head[u]=cnt;} inline int id(int A,int B,int C,int D){return A*(n+1)*(n+1)*(n+1)+B*(n+1)*(n+1)+C*(n+1)+D;} inline void tarjan(int u){ dfn[u]=low[u]=++tot,st[++top]=u,ins[u]=1; for(int i=Head[u];i;i=Next[i]){ if(!dfn[V[i]]) tarjan(V[i]),low[u]=min(low[u],low[V[i]]); else if(ins[V[i]]) low[u]=min(low[u],dfn[V[i]]); } if(dfn[u]==low[u]){ ++num;int k;do{ k=st[top--],belong[k]=num,siz[num]+=val[k],ins[k]=0; }while(k!=u); } } int main(){ //freopen("return.in","r",stdin); scanf("%d%d",&n,&m),num=(n+1)*(n+1)*(n+1)*n; for(int i=1;i<=n;++i){ int tmp=i;NUM a; for(int j=0;j<10;++j) while(tmp%P[j]==0) a.num[j]+=1,tmp/=P[j]; fac[i]=fac[i-1]*a; } for(int i=1;i<=m;++i){ scanf("%s",s),len=strlen(s); for(int j=0;j<len;++j) --trans[i][s[j]-'A'],++cost[i][s[j]-'A']; scanf("%s",s),len=strlen(s); for(int j=0;j<len;++j) ++trans[i][s[j]-'A']; } for(int i=0;i<=n;++i) for(int j=0;(i+j)<=n;++j) for(int k=0;(i+j+k)<=n;++k){ int now=id(i,j,k,n-i-j-k); val[now]=(fac[n]/fac[i]/fac[j]/fac[k]/fac[n-i-j-k]).getval(); for(int l=1;l<=m;++l){ if((!trans[l][0])&&(!trans[l][1])&&(!trans[l][2])&&(!trans[l][3])) continue; if((i>=cost[l][0])&&(j>=cost[l][1])&&(k>=cost[l][2])&&(n-i-k-j>=cost[l][3])) add(id(i+trans[l][0],j+trans[l][1],k+trans[l][2],n-i-j-k+trans[l][3]),now); } } for(int u=n;u<=(n+1)*(n+1)*(n+1)*n;++u) if(val[u]&&(!dfn[u])) tarjan(u); for(int u=n;u<=(n+1)*(n+1)*(n+1)*n;++u) if(val[u]) for(int i=Head[u];i;i=Next[i]) if(val[V[i]]) if(belong[V[i]]!=belong[u]) add(belong[u],belong[V[i]]),++in[belong[V[i]]]; for(int i=(n+1)*(n+1)*(n+1)*n;i<=num;++i) if(!in[i]) dis[i]=siz[i],Q.push(i); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=Head[u];i;i=Next[i]){ dis[V[i]]=max(dis[V[i]],dis[u]+siz[V[i]]),--in[V[i]]; if(!in[V[i]]) Q.push(V[i]); } }for(int i=(n+1)*(n+1)*(n+1)*n;i<=num;++i) ans=max(ans,dis[i]); printf("%lld\n",ans); }