日记详情

AtCoder abc470 F - Googol Swaps

分析

先考虑没有严格操作 \(10^{100}\) 次限制的方案数。

\(m\) 个可以交换的位置 \(A_i\) 和 \(B_i\)（\(i \in [1, m]\)），其实相当于在一个 \(n\) 个点的图上的 \(m\) 条边，在每个连通块内的元素是可以随意交换位置的。

记第 \(i\) 个连通块内点的数量为 \(sum_i\)，字符 \(c\) 的数量为 \(cnt_{i, c}\)。

第 \(i\) 个连通块的所有排列数（不考虑字符重复）为 \(A_{sum_i}^{sum_i}\)（即 \(sum_i!\)）。因为相同字符交换位置后仍看作同一方案，所以第 \(i\) 个连通块的真实方案数为：

\[\frac{A_{sum_i}^{sum_i}}{\displaystyle \prod_{c = \text{a}}^{\text{z}} A_{cnt_{i, c}}^{cnt_{i, c}}} \]

因此，若无操作次数限制，总方案数为对所有连通块求乘积：

\[ans = \prod_{i=1}^{cur} \frac{A_{sum_i}^{sum_i}}{\displaystyle \prod_{c} A_{cnt_{i, c}}^{cnt_{i, c}}} \]

操作次数必须为偶数（\(10^{100}\) 次），所以最终字符串对应的总置换必须为偶置换。

• 如果存在某个连通块内有重复字符：那么在这个块里交换两个相同字符的位置，不会改变字符串，但这个交换是一个奇置换。利用它，我们可以在不改变字符串的前提下，翻转总置换的奇偶性。因此，无论想要的排列对应置换的奇偶性如何，我们都能凑成偶数次操作。此时奇偶性限制对答案没有影响，答案就是 \(ans\)。

• 如果所有连通块内的字符都是互不相同的：则每个字符串只对应唯一的置换，并且该置换的奇偶性固定。而每个大小 \(\ge 2\) 的连通块内，所有排列中奇偶置换各占一半。要使最终字符串对应的总置换必须为偶置换，恰好只有一半的组合满足要求。因此答案为 \(ans / 2\)。

实现细节

使用并查集维护连通块信息。统计每个连通块的大小和各个字母的出现次数。利用预处理的阶乘 \(fac\) 和阶乘逆元 \(ifac\) 可以 \(O(1)\) 计算 \(A_n^m\) 及其逆。最后遍历所有连通块计算答案，并根据是否有重复字符决定是否乘上 \(\frac{1}{2}\)。

时间复杂度 \(O(n + m \alpha(n))\)，空间 \(O(n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll maxn=2e5+5;
const ll mod=998244353; 
struct DSU {ll n;vector<ll> f,cnt;void init() {for (ll i=1;i<=n;i++) f[i]=i,cnt[i]=1;}DSU (ll _n) {n=_n;f.resize(n+1),cnt.resize(n+1,0);init();}ll ask(ll x) {return f[x]==x?x:f[x]=ask(f[x]);}void add(ll x,ll y) {ll fx=ask(x),fy=ask(y);f[fx]=fy;cnt[fy]+=cnt[fx];}bool check(ll x,ll y) {return ask(x)==ask(y);}
};
ll powmod(ll x,ll y) {if (y==0) return 1;ll t=powmod(x,y/2);if (y&1) return x*t%mod*t%mod;else return t*t%mod;
}
ll n,m;
ll id[maxn],cnt[maxn][30],sum[maxn];
ll fac[maxn],ifac[maxn];
ll A(ll n,ll m) {return fac[n]*ifac[n-m]%mod;}
ll invA(ll n,ll m) {return ifac[n]*fac[n-m]%mod;}
ll inv(ll x) {return powmod(x,mod-2);}
void mod_mul(ll &x,ll y) {x=(x*y)%mod;}
void solve() {cin>>n>>m;string s;cin>>s;s=" "+s;DSU dsu(n);for (ll i=1;i<=m;i++) {ll a,b;cin>>a>>b;if (!dsu.check(a,b)) dsu.add(a,b);}ll cur=0;for (ll i=1;i<=n;i++) {ll bs=dsu.ask(i);if (id[bs]==0) id[bs]=++cur;cnt[id[bs]][s[i]-'a']++;sum[id[bs]]++;}ll ans=1,f=0;for (ll i=1;i<=cur;i++) {mod_mul(ans,A(sum[i],sum[i]));for (ll c=0;c<26;c++) {mod_mul(ans,invA(cnt[i][c],cnt[i][c]));f|=(cnt[i][c]>=2);}}cout<<ans*(f?1:inv(2))%mod<<endl;
}
int main() {fac[0]=1;for (ll i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod;ifac[maxn-1]=inv(fac[maxn-1]);for (ll i=maxn-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;ll t=1;
//	cin>>t;while (t--) solve();
}