题解：CF150B Quantity of Strings

YFF1 · 2024-11-24 18:11:07 · 题解

思路：

不难发现，如果把题目中要求的那些字符之间必须相等的关系抽象成图上的边，每个连通块内部都两两相等，就可以把这道题转化为一道基础图论题。注意到数据范围很小，所以我们可以把每个回文子串当中的每个下标枚举一遍，对应的字符看作给它们两个建了一条边，然后用并查集求解。不过答案可能很大，所以还要再加一个快速幂。

答案是什么呢？假设并查集求出来 p 个连通块，那么答案就是 m^p。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,mod=1e9+7,sum,fa[200005];
map<int,int>mp;
int find(int x){//并查集
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
int qpow(int a,int b){//快速幂
    int ans=1,cnt=a;
    while(b>0){
        if(b&1==1)ans=ans*cnt%mod;
        cnt=cnt*cnt%mod;
        b>>=1;
    }
    return ans;
}
signed main () {
    cin>>n>>m>>k;
    if(k>n){//注意这个情况，容易漏掉
        cout<<qpow(m,n)%mod;
        return 0;
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n-k+1;i++){
        for(int l=i,r=i+k-1;l<=r;l++,r--)fa[find(l)]=find(r);//建图
    } 
    for(int i=1;i<=n;i++)mp[find(i)]=1;//求连通块个数
    sum=qpow(m,mp.size());
    cout<<sum%mod;
    return 0;
}