abc470f 题解

· · 题解

诈骗题。

套路地，我们建 a_i 到 b_i 的双向边，则一个联通块内部的位置可以相互转化。

最终答案就是每个联通块的排列数相乘……吗？注意到 10^{100} 是一个偶数，所以我们不一定能取到进行奇数次操作的答案。

考虑什么时候能取到奇数的答案。发现实际上就是浪费一步，某一步交换两个相同的字符。虽然题目保证 a_i \neq b_i，但由于一个联通块内部的位置是可以相互转化的，则只要某个联通块内部包含相同的字符，就一定存在一种操作方式，使某一步交换到两个相同的字符，则可以取到完整的答案。这一结论是显然的，因为我们可以把操作数自由分配给每一个联通块，即可以更改整体操作数的奇偶性。

注意到进行偶数次操作和奇数次操作的答案应是完全对称的，所以取偶数的答案直接除 2 即可。

多重集排列公式：\frac{n!}{\prod cnt_i!}。

附赛时代码，赛后删掉了一些比较唐的注释。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 10;
const ll mod = 998244353;
int n, m;
string s;
int a[MAXN], b[MAXN];
vector<int> e[MAXN];
ll siz[MAXN], cnt[MAXN], fre[MAXN][26], tot;
bool vis[MAXN];
ll fact[MAXN], inv[MAXN];
bool is[MAXN];
ll qpow(ll x, ll y){
    ll res = 1;
    while(y){
        if(y & 1) res = (res * x) % mod;
        x = (x * x) % mod, y >>= 1;
    }
    return res;
}
void bfs(int st){
    queue<int> q; q.push(st);
    ++tot;
    ll mx = 0;
    while(q.size()){
        int u = q.front(); q.pop();
        if(vis[u]) continue;
        vis[u] = true, siz[tot]++;
        fre[tot][s[u] - 'a']++;
        mx = max(mx, fre[tot][s[u] - 'a']);
        for(auto &v : e[u])
            q.push(v);
    }
    is[tot] = (mx > 1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s, s = " " + s;
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    inv[n] = qpow(fact[n], mod - 2);
    for(int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % mod;
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> b[i];
        e[a[i]].push_back(b[i]), e[b[i]].push_back(a[i]);
    }
    for(int i = 1; i <= n; i++)
        if(!vis[i]) bfs(i);
    ll ans = 1;
    bool hav = false;
    for(int i = 1; i <= tot; i++){
        ll res = fact[siz[i]];
            for(int ch = 0; ch < 26; ch++)
                if(fre[i][ch]) res = (res * inv[fre[i][ch]]) % mod;
        hav |= is[i];
        ans = (ans * res) % mod;
    }
    if(!hav) ans = (ans * inv[2]) % mod;
    cout << ans;
    return 0;
}