题解：CF150B Quantity of Strings

思路：

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

答案是什么呢？假设并查集求出来

p

个连通块，那么答案就是

m^p

。

代码：

CPP

#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;
}

题解：CF150B Quantity of Strings

文章操作

思路：

代码：

相关推荐

评论

题解：CF150B Quantity of Strings