YbtOJ 604「强连通分量」字符变换

(Updated: )
oi
, ,

题目链接：YbtOJ #604

小 A 有一个长度为 $n$ 字符串 $s$，满足 $s$ 中只有 A,B,C,D 四种字符。

他还有 $m$ 个二元组，第 $i$ 个二元组可以用两个 等长 的字符串 $(a_i,b_i)$ 表示。

小 A 可以进行两种操作：

  1. 任意交换字符串 $s$ 中两个不同位置上的字符。
  2. 选择一个 $i$，截取 $s$ 中一个与 $a_i$ 相同的子串，将其替换为 $b_i$。

小 A 想要知道从 任意 初始字符串 $s$ 开始 连续 进行若干次变换，在这一过程中最多能得到多少种不同的字符串。

定义两个字符串不同，当且仅当它们存在至少一个位置上的字符不同。

$1\leq n\leq 30$，$1\leq m\leq 1000$。

Solution

考虑到可以任意交换字符，我们直接用三元组 $(x,y,z)$ 表示一种序列，序列中有 $x$ 个 A,$y$ 个 B,$z$ 个 C，那么显然就有 $(n-x-y-z)$ 个 D

那么，如果可以到达一种序列，能得到的字符串个数可以用可重排列数计算（即 $\frac{n!}{x!\cdot y!\cdot z!\cdot (n-x-y-z)!}$）。

一种序列能通过变换方式 $(a_i,b_i)$ 变成另一种序列，要满足四种字符的个数都大于等于 $a_i$ 中这些字符的个数。

若序列 A 能变成序列 B，我们就连一条从 A 向 B 的有向边。按这种方式建图，就是要求出从一个点出发最多能到达多少种不同的点，因此 Tarjan 给强连通分量缩点后拓扑跑一下就可以了。

求可重排列数的时候由于无法直接求 $n!$，可以先把每个数质因数分解然后抵消掉再乘起来。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=35,M=1010;
int n,m,id[N][N][N],cnt,s[N],v[N],pri[N],tot,l[M][4],r[M][4],fir[N*N*N],nxt[N*N*N*M<<1],son[N*N*N*M<<1],ttot,dfn[N*N*N],low[N*N*N],col[N*N*N],stk[N*N*N],cc,top,deg[N*N*N],ccnt;
LL Ans,d[N*N*N],S[N*N*N],w[N*N*N];
I void Add(CI x,CI y){x^y&&(nxt[++ttot]=fir[x],fir[x]=ttot,son[ttot]=y,0);}
#define to son[i]
char sa[N],sb[N];
I void GP(){RI i,j;for(i=2;i<=n;i++) for(!v[i]&&(pri[++tot]=i),j=1;j<=tot&&i*pri[j]<=n;j++) if(v[i*pri[j]]=1,!(i%pri[j])) break ;}
I LL QP(LL a,LL b){LL X=1;W(b) b&1&&(X*=a),a*=a,b>>=1;return X;}
I void Mark(RI x,CI v){RI i;for(i=1;i<=tot;i++) W(!(x%pri[i])) s[pri[i]]+=v,x/=pri[i];}
I void Tarjan(CI x){
    RI i;for(dfn[x]=low[x]=++ccnt,stk[++top]=x,i=fir[x];i;i=nxt[i]) if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);else if(!col[to]) low[x]=min(low[x],dfn[to]);
    if(dfn[x]==low[x]){col[x]=++cc,S[cc]+=w[x];W(stk[top]^x) col[stk[top]]=cc,S[cc]+=w[stk[top]],top--;top--;}
}
vector<int> G[N*N*N];
#define pb push_back
queue<int> q;
I void Topo(){
    RI i,u;for(i=1;i<=cc;i++) !deg[i]&&(q.push(i),d[i]=S[i]);W(!q.empty()){
        u=q.front(),q.pop();for(auto i:G[u]) d[i]=max(d[i],d[u]+S[i]),!--deg[i]&&(q.push(i),0);
    }return ;
}
int main(){
    freopen("character.in","r",stdin),freopen("character.out","w",stdout);
    RI i,i1,i2,i3,i4,j;LL t;for(read(n,m),GP(),i=1;i<=m;i++) for(scanf("%s%s",sa+1,sb+1),t=strlen(sa+1),j=1;j<=t;j++) l[i][sa[j]-'A']++,r[i][sa[j]-'A']--,r[i][sb[j]-'A']++;
    for(i1=0;i1<=n;i1++) for(i2=0;i1+i2<=n;i2++) for(i3=0;i1+i2+i3<=n;i3++){
        i4=n-i1-i2-i3,id[i1][i2][i3]=++cnt;for(j=1;j<=n;j++) Mark(j,1);
        for(j=1;j<=i1;j++) Mark(j,-1);for(j=1;j<=i2;j++) Mark(j,-1);for(j=1;j<=i3;j++) Mark(j,-1);for(j=1;j<=i4;j++) Mark(j,-1);
        for(t=1,j=1;j<=n;j++) t*=QP(j,s[j]),s[j]=0;w[cnt]=t;
    }for(i1=0;i1<=n;i1++) for(i2=0;i1+i2<=n;i2++) for(i3=0;i1+i2+i3<=n;i3++) for(i4=n-i1-i2-i3,j=1;j<=m;j++) i1>=l[j][0]&&i2>=l[j][1]&&i3>=l[j][2]&&i4>=l[j][3]&&(Add(id[i1][i2][i3],id[i1+r[j][0]][i2+r[j][1]][i3+r[j][2]]),0);
    for(i=1;i<=cnt;i++) !dfn[i]&&(Tarjan(i),0);for(i=1;i<=cnt;i++) for(j=fir[i];j;j=nxt[j]) if(col[i]^col[son[j]]) G[col[i]].push_back(col[son[j]]),deg[col[son[j]]]++;
    for(Topo(),i=1;i<=cc;i++) Ans=max(Ans,d[i]);return writeln(Ans),0;
}