ABC470F并查集+组合数学

· · 题解

写题解背景请看这篇。

我恨 C 题！

传送门

洛谷，AtCoder。

正文

::::info[分析] 题目无非就是给你一堆位置，你可以去交换这些位置上的字符。

我们可以把每个可能的交换想成一条无向边，建图，很容易发现，如果两个点不在一个联通块内，它们毫无关系，完全不会影响。

所以，我们只要统计各个联通块中的排列数，最后乘法原理就可以了。 :::: ::::info[计算] 假设没有 10^{100} 次的限制，每个连通块内有多少种方案呢？

假设这个连通块有 d 个字符，a 的个数为 c_0，b 的个数为 c_1，以此类推……z 的个数为 c_{25}。那排列这些字母有多少方案呢？

现将所有字符全排列，但因为相同字符可以互换位置，所以还要除以每个相同字符的全排列。

单个连通块内可组成 \frac{d!}{\prod_{i=0}^{25} c_i!} 种方案。 :::: ::::info[观察] 这个精确 10^{100} 显然不是让你去高精度，最多只是告诉你无限次，但是必须是偶数次。

那要求偶数次怎么处理呢？

现在假设原来的排列是 a，新的排列是 b。

从 a 变为 b 如果需要偶数次，那么就直接是符合要求的，但是如果是奇数次呢？

分两种情况讨论。 :::: ::::info[某个连通块内有相同字符] 假设连通块内，点 x 和 y 有一条边，相同的字符本来在点 p 和 q 的位置。

最终虽然原排列点 p 和 q 交换了位置，但是由于字符相同，并没有影响，但是步数和 t1+t2+1+t1+t2 是奇数，改变了奇偶性，使原来奇数次变为偶数次。 :::: ::::info[没有连通块内有相同字符] 那没救了。 :::: ::::info[统计] 因为每种交换需要步数都是 1，所以可以组成的每种排列所需步数是奇偶性对半开的，只要检测是否某个连通块内有相同字符，如果有，那就是全部，否则只有一半。 :::: ::::success[AC Code]

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define LL long long
#define F(i,k,n) for(int i=(k);i<=(n);++i)
#define RF(i,k,n) for(int i=(k);i>=(n);--i)
using namespace std;
const int MOD=998244353;
int fa[200005];
int ch[26];
int find(int x){
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void join(int x,int y){
    int xx=find(x);
    int yy=find(y);
    if(xx==yy)
        return;
    fa[xx]=yy;
    return; 
}
struct node{
    int x;
    int anc;
}sct[200005];
LL fac[200005];
LL inv[200005];
int fpow(LL x,int k){
    LL ans=1;
    while(k>0){
        if(k&1){
            (ans*=x)%=MOD;
        }
        k>>=1;
        (x*=x)%=MOD;
    }
    return ans;
}
void init(int n){
    fac[0]=1;
    F(i,1,n){
        fac[i]=fac[i-1]*i%MOD;
    }
    inv[n]=fpow(fac[n],MOD-2);
    RF(i,n-1,0){
        inv[i]=inv[i+1]*(i+1)%MOD;
    }
    return;
}
/*int c(int x,int y){
    return fac[x]*inv[x-y]%MOD;
}*/
bool cmp(node x,node y){
    return x.anc<y.anc;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    init(n);
    string s;
    cin>>s;
    s=' '+s;
    F(i,1,n){
        fa[i]=i;
    }
    F(i,1,k){
        int u,v;
        cin>>u>>v;
        join(u,v);
    }
    F(i,1,n){
        sct[i].anc=find(i);
        sct[i].x=i;
    }
    sort(sct+1,sct+n+1,cmp);
    LL ans=1;
    vector<int>v;
    bool bl=0;
    F(i,1,n){
        if(i!=1&&sct[i].anc!=sct[i-1].anc){
            memset(ch,0,sizeof(ch));
            for(int it:v){
                ++ch[s[it]-'a'];
            }
            LL sum=fac[v.size()];
            F(j,0,25){
                if(ch[j]>1){
                    bl=1;
                }
                (sum*=inv[ch[j]])%=MOD;
            }
            (ans*=sum)%=MOD;
            v.clear();
        }
        v.push_back(sct[i].x);
    }
    memset(ch,0,sizeof(ch));
    for(int it:v){
        ++ch[s[it]-'a'];
    }
    LL sum=fac[v.size()];
    F(i,0,25){
        if(ch[i]>1){
            bl=1;
        }
        (sum*=inv[ch[i]])%=MOD;
    }
    (ans*=sum)%=MOD;
    if(bl)
        cout<<ans;
    else
        cout<<ans*inv[2]%MOD;
    return 0;
}

提交记录。 ::::