题解：AT_abc470_f [ABC470F] Googol Swaps

· · 题解

过 F 不过 C 选手。

我说 A<B<F<<<<<D<C<G<E 有没有懂的。

一种比较好想的建模方式：把 N 个位置看作 N 个点，M 个交换方式看作 M 条无向边。那么这样能得到若干个连通块。

大胆猜测同一个连通块经过无限次交换后能得到原序列的所有排列。证明非常简单，若对于一个新排列，s_i 在位置 j，由于是连通块，必能通过若干次交换得到，故 s_i 移动到位置 j 可行。同理，其它字符的移动也必然可行。证毕。

那么就非常简单了，用并查集跑出每一个连通块，对每一个连通块內部单独算组合数。若一个连通块内有 A 个 a,B 个 b,\cdots,Z 个 z，那么共有 \frac{(A+B+\cdots+Z)!}{A!B!\cdots Z!}，也就是先对所有元素求一个全排列，再除去相同元素内部的全排列方案数。

由于交换次数是 10^{100} 次，而非传统意义的无限次，还需考虑一下奇偶排列。当每个连通块内都不存在相同元素，即任意一次交换都会产生新的排列（改变奇偶性），需对结果除以二，经过偶数次交换后，必然只能得到奇排列/偶排列其一。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10, mod = 998244353;
int n, m, fa[maxn], sz[maxn];
int cnt[maxn][26];//cnt用于记录每个并查集所包含各个字母的数量 
string s;
int fac[maxn], ifac[maxn];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int qpow(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1)r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s, s = "-" + s;
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;//预处理阶乘及其逆元 
    for (int i = 1; i <= n; i++) {
        fa[i] = i, sz[i] = 1;
        cnt[i][s[i] - 'a'] = 1;
    }//并查集初始化 
    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        int x = find(a), y = find(b);
        if (x == y) continue;
        if (sz[x] < sz[y]) swap(x, y);
        fa[y] = x, sz[x] += sz[y];
        for (int i = 0; i < 26; i++) cnt[x][i] += cnt[y][i];
    }
    int ans = 1, flag = 0;
    for (int i = 1; i <= n; i++) {
        if (find(i) != i) continue;
        int tot = fac[sz[i]];
        for (int c = 0; c < 26; c++) {
            tot = tot * ifac[cnt[i][c]] % mod;//除去相同字符内部排列数 
            if (cnt[i][c] >= 2) flag = 1;
        }
        ans = ans * tot % mod;
    }
    if (!flag) ans = ans * qpow(2, mod - 2) % mod;
    cout << ans;
    return 0;
}