【题目来源】

AtCoder：F - Googol Swaps

【题目描述】

You are given a string \(S\) of length \(N\) consisting of lowercase English letters.
Find the number, modulo \(998244353\), of strings that \(S\) can become after performing the following operation exactly \(10^{100}\) times.

Choose an integer \(i\) between \(1\) and \(M\), inclusive, and swap the \(A_i\)-th and \(B_i\)-th characters of \(S\).

给定一个长度为 \(N\)、由小写英文字母组成的字符串 \(S\)。

求将以下操作恰好执行 \(10^{100}\) 次后，\(S\) 能变成的字符串数量，对 \(998244353\) 取模。

选择 \(1\) 到 \(M\) 之间（含）的整数 \(i\)，并交换 \(S\) 的第 \(A_i\) 个字符和第 \(B_i\) 个字符。

【输入】

The input is given from Standard Input in the following format:

\(N\) \(M\)
\(S\)
\(A_1\) \(B_1\)
\(\vdots\)
\(A_M\) \(B_M\)

【输出】

Output the answer.

【输入样例】

5 3
miria
1 3
2 5
4 5

【输出样例】

【核心思想】

问题分析：给定字符串 \(S\) 和 \(M\) 对可交换位置，求恰好执行 \(10^{100}\) 次交换后能得到的字符串数量（模 \(998244353\)）。由于 \(10^{100}\) 是极大的偶数，核心观察是：交换操作生成一个置换群，恰好执行 \(10^{100}\) 次等价于在群中取 \(10^{100}\) 次幂。通过并查集找到交换操作生成的连通块，每个连通块内字符可任意重排，但偶数次操作限制了某些排列的可达性。
算法选择：
- 并查集：找到由交换操作连接的连通块，每个连通块内的位置可自由交换
- 多重集排列：每个连通块内的字符串排列数为 \(\frac{siz!}{\prod cnt_c!}\)
- 群论分析：若连通块内无重复字符，所有排列的阶为 \(2\)（交换生成对称群 \(S_{siz}\)，但 \(10^{100}\) 为偶数，只有偶排列可达，方案数需除以 \(2\)）
关键步骤：
- 初始化：读取 \(N\)、\(M\)、\(S\)，并查集初始化
- 建图合并：读入 \(M\) 对交换位置 \((A_i, B_i)\)，用并查集合并
- 预处理阶乘和逆元：\(fac[i] = i! \bmod mod\)，\(invfac[i] = (i!)^{-1} \bmod mod\)（费马小定理）
- 按连通块分组：统计每个连通块包含的位置和字符频率
- 计算答案：
  - 对每个连通块，计算多重集排列数 \(ways = \frac{siz!}{\prod cnt_c!}\)，累乘到 \(ans\)
  - 检查连通块内是否有重复字符：若有，\(flag = false\)（存在不动点，偶数次操作不影响计数）
  - 若所有连通块内字符均不重复（\(flag = true\)）：\(ans = ans \times 2^{-1} \bmod mod\)（只有偶排列可达）
- 输出答案 \(ans\)
时间/空间复杂度：
- 时间复杂度：\(O(N \alpha(N) + N \log mod)\)，并查集近乎线性，阶乘预处理和快速幂为 \(O(N \log mod)\)
- 空间复杂度：\(O(N)\)，并查集、阶乘数组、连通块分组
置换群与组合数学的核心思想：
- 连通块独立性：不同连通块的位置互不连通，字符无法跨块交换，总方案数为各连通块方案数的乘积
- 多重集排列：连通块内字符可任意排列，但相同字符不可区分，用多重集排列公式计算
- 偶数次操作的约束：当连通块内无重复字符时，交换操作生成完整的对称群，但 \(10^{100}\) 为偶数意味着只有偶排列（可分解为偶数个对换）可达，方案数减半
- 有重复字符的特殊性：若连通块内有重复字符，存在非恒等排列在偶数次操作后仍可达（因交换相同字符不改变字符串），无需额外除法
- 适用于置换群计数、组合数学、并查集连通性分析类问题

【算法标签】

排列组合

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long // 使用long long防止中间计算溢出
const int N = 200005, mod = 998244353; // N:最大字符串长度, mod:模数
int n, m; // n:字符串长度, m:可交换的位置对数
string s; // 原始字符串
int a[N], b[N]; // a[i]/b[i]:第i对可交换的位置（本题中未直接使用数组）
int p[N]; // 并查集父节点数组
int fac[N], invfac[N]; // fac:阶乘数组, invfac:阶乘逆元数组
map<int, vector<int>> groups; // 每个连通块包含的所有位置// 并查集查找：带路径压缩
int find(int x)
{if (p[x]!=x) p[x] = find(p[x]);return p[x];
}// 并查集合并
void merge(int a, int b)
{a = find(a), b = find(b);if (a != b)p[a] = b;
}// 快速幂：计算a^b % mod
int qmi(int a, int b)
{int res = 1;while (b){if (b&1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}signed main()
{cin >> n >> m >> s; // 读入字符串长度、交换对数和字符串s = " " + s; // 字符串下标从1开始// 初始化并查集for (int i=1; i<=n; i++)p[i] = i;// 读入m对可交换位置，并在并查集中合并for (int i=1; i<=m; i++){int a, b;cin >> a >> b;merge(a, b);}// 预处理阶乘数组fac[0] = 1;for (int i=1; i<=n; i++)fac[i] = fac[i-1] * i % mod;// 预处理阶乘逆元数组（费马小定理）invfac[n] = qmi(fac[n], mod-2);for (int i=n-1; i>=1; i--)invfac[i] = invfac[i+1] * (i+1) % mod;// 按连通块分组：每个根节点对应一个位置向量for (int i=1; i<=n; i++)groups[find(i)].push_back(i);int ans = 1; // 最终答案bool flag = true; // 标记是否所有连通块内字符都不重复// 遍历每个连通块，计算该连通块内的排列数for (auto t : groups){int root = t.first; // 连通块的根节点vector<int> vec = t.second; // 该连通块包含的所有位置int siz = vec.size(); // 连通块大小map<char, int> cnt; // 统计该连通块内每种字符的出现次数for (auto idx : vec)cnt[s[idx]]++;// 计算该连通块内的不同排列数：多重集排列公式 siz! / (c1! * c2! * ...)int ways = fac[siz];for (auto t : cnt){char c = t.first;int cnum = t.second;ways = ways * invfac[cnum] % mod;}ans = ans * ways % mod; // 各连通块独立，答案相乘// 检查该连通块内是否有重复字符bool hasDuplicate = false;for (auto t : cnt){char c = t.first;int cnum = t.second;if (cnum>=2){hasDuplicate = true;break;}}// 如果有重复字符，说明存在不动点（某些排列执行偶数次后回到原串）if (hasDuplicate)flag = false;}// 如果所有连通块内字符都不重复，则每个排列的阶都是2// 执行10^100次（偶数次）后，只有恒等排列能回到原串// 所以方案数需要除以2（乘以2的逆元）if (flag)ans = ans * qmi(2, mod-2) % mod;cout << ans << endl; // 输出最终答案return 0;
}

【运行结果】

5 3
miria
1 3
2 5
4 5
6

日记详情

题解：AtCoder AT_abc470_f Googol Swaps

排列组合