又想起了当初在TC上刷网络流的时候被submitfailed支配一下午的恐惧。。。
题解：
发现由于我们允许交换任意两个位置的字符，对我们唯一有用的就只剩下字符个数，30的不超过4个的有序非负整数拆分有545654565456种，权值显然就是n!a!b!c!d!\frac{n!}{a!b!c!d!}a!b!c!d!n!，直接组合数算一下即可，连边可以直接暴力连，那么缩一个SCC之后就是拓扑序DP求DAG最长链了。
由于是考场代码改的，并不是我一贯的在TopCoder上做题的代码风格，好吧估计也没人关心我的TopCoder代码风格是什么样子
代码：
#include<bits/stdc++.h>#definelllonglong#definereregister#definecsconstusingstd::cerr;usingstd::cout;csintN=31,M=6e3+7;//30的有序正整数拆分只有5456种intn;intid[N][N][N][N],tot;llw[M],C[N][N];std::vector<int>G[M];inlinevoidinit(){for(intrei=0;i<=30;++i){C[i][0]=1;for(intrej=1;j<=i;++j)C[i][j]=C[i-1][j-1]+C[i-1][j];}}inlinellcalc(inta,intb,intc,intd){llans=1;ans*=C[n][a];ans*=C[n-a][b];ans*=C[n-a-b][c];ans*=C[n-a-b-c][d];returnans;}intdfn[M],low[M],dfc;intscc[M],inst[M],st[M],tp,sct;voidtarjan(intu){inst[u]=true;st[++tp]=u;dfn[u]=low[u]=++dfc;for(intree=G[u].size()-1;~e;--e){intv=G[u][e];if(!dfn[v]){tarjan(v);low[u]=std::min(low[u],low[v]);}elseif(inst[v])low[u]=std::min(low[u],dfn[v]);}if(dfn[u]==low[u]){++sct;while(true){intv=st[tp--];scc[v]=sct;inst[v]=false;if(v==u)break;}}}namespaceDAG{intel[M],nxt[M*100],to[M*100],ect;llw[M],f[M];intd[M],q[M],qn;inlinevoidadde(intu,intv){nxt[++ect]=el[u],el[u]=ect,to[ect]=v,++d[v];}inlinevoidtop_sort(){for(intrei=1;i<=sct;++i)if(!d[i])q[++qn]=i;for(intrei=1;i<=qn;++i){intu=q[i];for(intree=el[u],v=to[e];e;v=to[e=nxt[e]])if(!--d[v])q[++qn]=v;}for(intrei=qn;i;--i){intu=q[i];llt=0;for(intree=el[u],v=to[e];e;v=to[e=nxt[e]])t=std::max(t,f[v]);f[u]=w[u]+t;}}inlinellsolve(){for(intreu=1;u<=tot;++u){w[scc[u]]+=::w[u];for(intree=G[u].size()-1;~e;--e){intv=G[u][e];if(scc[u]!=scc[v])adde(scc[u],scc[v]);}}top_sort();llans=0;for(intrei=1;i<=sct;++i)ans=std::max(ans,f[i]);returnans;}}usingstd::string;classImpossibleGame{public:llgetMinimum(intk,std::vector<string>before,std::vector<string>after){n=k;init();for(inta=0;a<=n;++a)for(intb=0;a+b<=n;++b)for(intc=0;a+b+c<=n;++c){intd=n-a-b-c;id[a][b][c][d]=++tot;w[tot]=calc(a,b,c,d);}for(intrei=0;i<before.size();++i){autos=before[i],t=after[i];intca=0,cb=0,cc=0,cd=0;intcA=0,cB=0,cC=0,cD=0;for(intrei=0;i<s.size();++i){switch(s[i]){case'A':++ca;break;case'B':++cb;break;case'C':++cc;break;case'D':++cd;break;}switch(t[i]){case'A':++cA;break;case'B':++cB;break;case'C':++cC;break;case'D':++cD;break;}}if(ca==cA&&cb==cB&&cc==cC&&cd==cD)continue;cA-=ca,cB-=cb,cC-=cc,cD-=cd;for(inta=ca;a<=n;++a)for(intb=cb;a+b<=n;++b)for(intc=cc;a+b+c<=n;++c){intd=n-a-b-c;if(d<cd)continue;intA=a+cA,B=b+cB,C=c+cC,D=d+cD;G[id[a][b][c][d]].push_back(id[A][B][C][D]);}}for(intrei=1;i<=tot;++i)if(!dfn[i])tarjan(i);returnDAG::solve();}};#ifdefzxyoiImpossibleGameSolver;signedmain(){std::cout<<Solver.getMinimum(6,{"AABBC","AAAADA","AAACA","CABAA","AAAAAA","BAAAA"},{"AACCB","DAAABC","AAAAD","ABCBA","AABAAA","AACAA"})<<"\n";return0;}#endif
