题解：AT_abc470_f [ABC470F] Googol Swaps

· · 题解

由于是 10^{100} 次操作，我们可以钦定操作数量无限多。我们可以直接先求出所有的连通块，然后容易发现我们可以对里面的元素任意排序。

于是，对于每个连通块，记 c_i 表示字母 i 的出现次数，答案就是

(\sum c_i)!\prod \dfrac{1}{c_i!}

的乘积……吗？

我们发现，它还有一个问题，就是我们要操作恰好 10^{100} 次！如果我们单个连通块内有两个字母相同，就不用担心这个了，但是如果没有呢？

于是我们发现，如果我们最后交换的次数少一次，我们就必须选择两个字母交换，由于它们一定不同，相当于这两个字母的排列从 2 种变成了一种，所以答案要 \times \frac{1}{2}。于是我们就做完了。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353;
constexpr int maxn=1010101;
int f[maxn];
#define find _find
__inline int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
vector<int> e[maxn];
long long fac[maxn];
int cnt[30];
__inline long long qpow(long long base,int p=mod-2){
    long long ans=1;
    while(p){
        if(p&1)ans=ans*base%mod;
        base=base*base%mod;
        p>>=1;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m;cin>>n>>m;
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=n;i++)f[i]=i;
    string s;cin>>s;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        f[find(a)]=find(b);
    }
    for(int i=1;i<=n;i++)e[find(i)].push_back(s[i-1]);
    long long ans=1;
    bool flg=0;
    for(int i=1;i<=n;i++){
        sort(e[i].begin(),e[i].end());
        memset(cnt,0,sizeof(cnt));
        for(auto x:e[i])cnt[x-'a']++;
        ans=ans*fac[e[i].size()]%mod;
        for(int i=0;i<26;i++){
            ans=ans*qpow(fac[cnt[i]])%mod;
            if(cnt[i]>1)flg=1;
        }
    }
    if(!flg)ans=ans*qpow(2)%mod;
    cout<<ans<<'\n';
    return 0;
}