AT_abc470_f

jojo222 · 2026-08-08 22:41:04 · 题解

为什么题目中把恰好 10^{100} 次标粗了呢？
考虑 ab，只能交换 1 和 2，此时交换偶数次一定不变。

对，我的意思是说，你不能把 10^{100} 当成任意。

把交换方案当成边，算出组成的联通块，此时联通块内部可以较为自由地排列。

如果任何一个联通块中有相同的字符，就可以无视奇偶性的要求。

除了这种特殊情况，我们可以猜测， :::success[单个联通块交换奇/偶数次的方案数 w 是总的一半] 给字母编号为 1,2,\cdots,26，当交换两个数时，什么的奇偶性一定会变化呢？
逆序对。假设交换了 x,y(x<y)，那么 x 左边的和 y 右边的贡献不变，而 (x,y) 这一对会产生 1 的变化。

• 若原来 a_x<a_y，那么交换后 x 会多贡献 (a_x,a_y) 这个区间，y 也一样，加起来一定是偶数。
• ::: :::success[答案也是原来的一半] 交换次数一定是偶数，所以“单个联通块交换奇数次”只能选偶数次，在 $m$ 个联通块中选 $i$ 个“交换奇数次”的方案数是 $\prod w\times C_m^i$，然后 $\prod w$ 可以消掉。 设 $k$ 为非负整数，显然 $\sum_{i=2k}C_m^i=\sum_{i=2k+1}C_m^i$。 ::: ```cpp int n, m, x, y, ans = 1, f[200005]; bool fl; string s; vector<int> b; unordered_map<char, int> mp; signed main() { read(n, m, s), setfac(f, n, m99); dsu a(n); rep(i, 1, m) read(x, y), a.unite(x, y); rep(i, 1, n) if(a.find(i) == i) { mp.clear(), b.pb(1); for(int x : a.mp[i]) mp[s[x-1]]++; int s = a.siz[i]; for(auto [v, c] : mp) { if(c > 1) fl = 1; b.back() = b.back() * C(f, s, c, m99) % m99, s -= c; } } for(int x : b) ans = ans * x % m99; write(fl ? ans : qdiv(ans, 2, m99)); return 0; } ```