[TC11326]ImpossibleGame
题目大意：
一类字符串仅由'A','B','C','D'四种字母组成。对于这样的一个字符串\(S\)，可以用以下两种方式之一修改这个字符串：
- 交换\(S\)中的相邻两个字母；
- 使用一种魔法。魔法共\(m(m\le50)\)种，其中第\(i\)种可以将\(S\)中一个等于\(X_i\)的子串替换为\(y_i\)，保证\(|X_i|=|Y_i|\)。
求对于所有这样的长度为\(n(n\le30)\)的字符串\(S\)，修改过程中出现的不同的字符串最多能有多少？
思路：
对于第一种操作，显然若两个字符串中各字符出现次数对应相等，则这两个字符串之间可以相互转化。
因此我们可以用一个三元组\((a,b,c)\)表示字符串的状态，其中\(a,b,c\)分别表示字符'A','B','C'出现的次数。
魔法就相当于在这些状态间连边。
缩点后在DAG上DP即可。
时间复杂度\(\mathcal O(n^3m)\)
源代码：
#include<stack>
#include<queue>
#include<string>
#include<vector>
class ImpossibleGame {
private:
using int64=long long;
static constexpr int N=31,S=5457;
int64 fac[N],w[S],f[S];
int id[N][N][N],tot,a[S],b[S],c[S],d[S];
void init(const int &n) {
for(register int i=fac[0]=1;i<=n;i++) {
fac[i]=fac[i-1]*i;
}
for(register int i=0;i<=n;i++) {
for(register int j=0;i+j<=n;j++) {
for(register int k=0;i+j+k<=n;k++) {
const int l=n-i-j-k;
id[i][j][k]=++tot;
a[tot]=i;
b[tot]=j;
c[tot]=k;
d[tot]=l;
w[tot]=fac[n]/fac[i]/fac[j]/fac[k]/fac[l];
}
}
}
}
struct Edge {
int u,v;
};
std::vector<Edge> edge;
std::vector<int> e[S];
inline void add_edge(const int &u,const int &v) {
e[u].emplace_back(v);
}
bool ins[S];
std::stack<int> s;
int dfn[S],low[S],scc[S],ind[S];
void tarjan(const int &x) {
dfn[x]=low[x]=++dfn[0];
s.push(x);
ins[x]=true;
for(auto &y:e[x]) {
if(!dfn[y]) {
tarjan(y);
low[x]=std::min(low[x],low[y]);
} else if(ins[y]) {
low[x]=std::min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]) {
int y;
scc[0]++;
do {
y=s.top();
s.pop();
ins[y]=false;
scc[y]=scc[0];
f[scc[0]]+=w[y];
} while(y!=x);
}
}
std::queue<int> q;
int64 dis[S];
int64 kahn() {
for(register int i=1;i<=scc[0];i++) {
if(!ind[i]) {
dis[i]=f[i];
q.push(i);
}
}
int64 ret=0;
while(!q.empty()) {
const int x=q.front();
q.pop();
for(auto &y:e[x]) {
dis[y]=std::max(dis[y],dis[x]+f[y]);
if(!--ind[y]) {
q.push(y);
}
}
ret=std::max(ret,dis[x]);
}
return ret;
}
public:
int64 getMinimum(const int &n,const std::vector<std::string> &s,const std::vector<std::string> &t) {
init(n);
const int m=s.size();
for(register int i=0;i<m;i++) {
int w=0,x=0,y=0,z=0,o=0,p=0,q=0,r=0;
const int l=s[i].length();
for(register int j=0;j<l;j++) {
if(s[i][j]=='A') w++;
if(s[i][j]=='B') x++;
if(s[i][j]=='C') y++;
if(s[i][j]=='D') z++;
if(t[i][j]=='A') o++;
if(t[i][j]=='B') p++;
if(t[i][j]=='C') q++;
if(t[i][j]=='D') r++;
}
for(register int i=1;i<=tot;i++) {
if(a[i]<w||b[i]<x||c[i]<y||d[i]<z) continue;
const int &j=id[a[i]-w+o][b[i]-x+p][c[i]-y+q];
if(i==j) continue;
add_edge(i,j);
edge.emplace_back((Edge){i,j});
}
}
for(register int i=1;i<=tot;i++) {
if(!dfn[i]) tarjan(i);
}
for(register int i=1;i<=tot;i++) {
e[i].clear();
}
for(auto &e:edge) {
const int &u=e.u,&v=e.v;
if(scc[u]!=scc[v]) {
add_edge(scc[u],scc[v]);
ind[scc[v]]++;
}
}
return kahn();
}
};