题解：AT_abc470_f [ABC470F] Googol Swaps

· · 题解

思路

首先 10^{100} 是一个偶数。

我们不难知道，通过偶数次交换可以产生的字符串一定可以通过 10^{100} 次交换产生，因为之后一直交换 A_1 和 B_1 直到 10^{100} 次就可以了。

那么问题来了，奇数次交换得到的字符串可不可以用 10^{100} 次交换产生呢？答案是不一定行。

我们思考一种奇偶性转化，使得一个同样的字符串，原本需要奇数次交换产生，让它也可以通过偶数次交换产生。即，交换一对相同的字符。

考虑用连通块实现，如果 i 和 j 在同一连通块，则代表 S_i 和 S_j 可以直接或间接的进行交换，则如果有一对 (i,j) 满足 S_i=S_j 且 i 和 j 在同一连通块内，奇数次交换得到的字符串可以用 10^{100} 次交换产生。

代码实现

连通块可以用 DFS 实现。

不难想到，奇数次交换得到的字符串必定与偶数次交换可以产生的字符串数量相等。如果有一对 (i,j) 满足 S_i=S_j 且 i 和 j 在同一连通块内，则输出所有通过交换可能得到的字符串数量，否则再除以 2。

每个连通块 K 通过交换可能得到的字符串数量为 \frac{\text{size}_K!}{\prod_{c=0}^{25}({\text{cnt}_c})!}，其中 \text{cnt}_c 为每个字符的出现次数，\text{size}_K 为连通块大小。所有可能即为所有连通块可能的乘积。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,MOD=998244353;
int n,m,vis[N],fl=0;
long long ans=1,po[N],inv[N];
string s;
vector<int> e[N];
vector<int> com;
void dfs(int x){
    if(vis[x]) return ;
    vis[x]=1;
    com.push_back(x);
    for(int i:e[x]) dfs(i);
}
long long ksm(long long x,long long y){
    long long res=1;
    while(y){
        if(y%2) res=res*x%MOD;
        x=x*x%MOD;
        y>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    s=' '+s;
    po[0]=1;
    for(int i=1;i<=n;i++) po[i]=po[i-1]*i%MOD;
    inv[n]=ksm(po[n],MOD-2);
    for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%MOD;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        com.clear();
        dfs(i);
        int cnt[30];
        for(int j=0;j<26;j++) cnt[j]=0;
        for(int j:com) cnt[s[j]-'a']++;
        for(int j=0;j<26;j++){
            if(cnt[j]>1){
                fl=1;
                break;
            }
        }
        long long ways=po[com.size()];
        for(int c=0;c<26;c++) ways=ways*inv[cnt[c]]%MOD;
        ans=ans*ways%MOD;
    }
    if(!fl) ans=ans*ksm(2,MOD-2)%MOD;
    cout<<ans;
    return 0;
}