题解：AT_abc470_f [ABC470F] Googol Swaps
Frums
·
·
题解
观前提醒：题解中的每个在原题面中出现过的变量含义均与原题相同。
Atcoder 题目传送门
思路
对于每个 A_i 与 B_i 我们连一条无向边，不难发现每个连通块的答案相互独立，可以先算每个连通块内的答案数量然后用乘法原理乘起来。
题目说必须交换 10^{100} 次，非常大，可以认为交换次数无限，也就是排列数。但是！题目没有保证没有相同的字符，所以就是排列数的一种特殊类型：可重集的排列。
可重集的排列其实非常简单啦。设联通块内每个字母出现的次数为 t_i，连通块大小为 siz，排列数为 \frac{siz!}{t_1!\times t_2!\times \cdots t_{26}!}，快速幂求一下逆元即可。
坑点
写到这里你会发现样例 2 过不了，然后你手摸一遍发现没问题啊，就是 36 啊，为啥样例输出是 18，然后你就会被卡半个小时。
（估计只有我这么唐）。
问题出在这句话上：必须交换 10^{100} 次，非常大，可以认为交换次数无限。
然后样例 $1$ 和 $3$ 过不了了，不难发现，如果存在一个 $i$，使得 $S_{A_i}=S_{B_i}$，需要交换奇数次的排列也可以达成了。特判一下即可。
---
::::success[AC Code]
```cpp
#include<bits/stdc++.h>
#define wef(i,l,r) for(int i=l;i<=r;i++)
#define few(i,r,l) for(int i=r;i>=l;i--)
#define re read()
#define pii pair<int,int>
#define endl putchar('\n')
using ll=long long;
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
inline bool write(auto x,char fg=0){bool neg=0;if(x<0){neg=1;putchar('-');}static int sta[40];int top=0;do{sta[top++]=x%10;x/=10;}while(x);if(neg) while(top) putchar('0'-sta[--top]); else while(top) putchar('0'+sta[--top]);if(fg) putchar(fg);return 0;}
const int N=3e5+5,mod=998244353;
#define int long long
string a;
vector<int> g[N];
int t[N][26],v[N],cnt;
void dfs(int x){
t[cnt][a[x]-'a']++;
for(int y:g[x]){
if(v[y]) continue;
v[y]=1;
dfs(y);
}
}
int fac[N];
inline int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
b>>=1,a=a*a%mod;
}
return res;
}
signed main(){
int n=re,m=re;
cin>>a;
a=" "+a;
wef(i,1,m){
int x=re,y=re;
g[x].push_back(y);
g[y].push_back(x);
}
bool free=0,lar=0;
wef(i,1,n){
if(!v[i]){
v[i]=1;
cnt++;
dfs(i);
int sum=0;
bool dup=0;
wef(j,0,25){
sum+=t[cnt][j];
if(t[cnt][j]>=2) dup=1;
}
if(sum>=2){
lar=1;
if(dup) free=1;
}
}
}
fac[0]=1;
wef(i,1,n) fac[i]=fac[i-1]*i%mod;
int res=1;
if(!free&&lar) res=qpow(2,mod-2);
wef(i,1,cnt){
int sum=0, mul=1;
wef(j,0,25){
mul=fac[t[i][j]]*mul%mod;
sum+=t[i][j];
}
res=res*fac[sum]%mod*qpow(mul,mod-2)%mod;
}
write(res);
return 0;
}
```
::::