题解：AT_abc470_f [ABC470F] Googol Swaps
chenyongxi3
·
·
题解
更好的阅读体验？
我说 E > C > F > D 有没有懂的。
根据题目限制建图。
:::info[引理 1]{open}
在一个连通分量中，通过有限次交换即可达到所有可能的情况。
:::
:::success[证明]
考虑任意一对点 (x,y)。一定存在至少一条无环的路径（也就是链）。设路径上的点分别是 x,g_1,g_2,g_3,\ldots,g_h,y。则我们考虑以下策略：
先依次交换 (x,g_1),(x,g_2),(x,g_3),\ldots,(x,g_h),(x,y)，此时这条链变为 g_1,g_2,g_3,\ldots,g_h,y,x；
再依次交换 (y,g_h),(y,g_{h-1}),\ldots,(y,g_1)。此时这条链变为 y,g_1,g_2,g_3,\ldots,g_h,x。
于是我们就可以在有限步内任意交换一对，自然可以达到所有情况。
:::
:::info[引理 2]{open}
设 c_{i,ch} 表示 ch 在连通分量 i 里出现了 c_{i,ch} 次，则这个连通分量总的可能方案数即
\frac{(\sum_{p} c_{i,p})!}{\prod_p (c_{i,p}!)}
其中分子即连通分量大小。
:::
:::success[证明]
小学数学。
设该连通分量的大小为 sz，则有 sz! 种排列，但是每一个字符在它自己内部的排列不影响总排列个数，因此以此除以每一个字符个数的阶乘即可。
:::
:::info[引理 3]{open}
如果任意连通分量中有重复字符，则答案即
\sum_i (\frac{(\sum_{p} c_{i,p})!}{\prod_p (c_{i,p}!)})
否则，答案需要除以二。
:::
:::success[证明]
设我们有一个联通分两种有重复字符，则我们先把它们换到一起，然后左手倒右手，最后再从这个状态出发去目标状态。因为不管我们给这两个字符交换多少次都不会有实质性的变换，因此我们就可以控制总次数的奇偶，所有排列便均可达。
否则，最终排列的奇偶性必须与原来相同。
在每个连通分量中，其大小为 $sz$，由于字符互不相同，则总排列有 $sz!$ 种，其中奇排列和偶排列各占一半，这可以通过一次交换使得两个排列一一对应证明。于是答案即原来的一半。
:::
把引理拼起来，就得到了算法的完整步骤：
利用并查集维护连通分量中的元素，然后对每个连通分量计算答案，最后统计。
贴个代码。马蜂略丑，轻喷。
:::success[code]
```cpp
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
constexpr int mod=998244353;
struct DSU{
int fa[200005];
DSU(int n){
for(int i=1;i<=n;i++)fa[i]=i;
}
int Find(int x){
if(fa[x]==x)return x;
return fa[x]=Find(fa[x]);
}
void Union(int x,int y){
int a=Find(x);
int b=Find(y);
if(a==b)return;
fa[a]=b;
}
};
ll qmi(ll x,ll p){
ll res=1;
while(p){
if(p&1)res=res*x%mod;
x=x*x%mod;
p>>=1;
}
return res;
}
ll fact[200005],invfact[200005];
void init(int n){
fact[1]=1;
for(int i=2;i<=n;i++)fact[i]=fact[i-1]*i%mod;
invfact[n]=qmi(fact[n],mod-2);
for(int i=n-1;i>=1;i--)invfact[i]=invfact[i+1]*(i+1)%mod;
}
vector<int>group[200005];
int cnt[26];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m;
string s;
cin>>n>>m>>s;
s=' '+s;
DSU d(n+1);
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
d.Union(u,v);
}
init(n+1);
for(int i=1;i<=n;i++)group[d.Find(i)].push_back(i);
bool flg=false;
ll ans=1;
for(int i=1;i<=n;i++){
if(group[i].size()==0)continue;
memset(cnt,0,sizeof(cnt));
for(int id:group[i]){
int t=s[id]-'a';
cnt[t]++;
if(cnt[t]>1)flg=true;
}
ll res=fact[group[i].size()];
for(int j=0;j<26;j++)if(cnt[j]>1)res=res*invfact[cnt[j]]%mod;
ans=ans*res%mod;
}
if(flg){
cout<<ans;
}else{
cout<<ans*499122177ll%mod;
}
}
/*
*/
```
:::