此题因为要求划分段数小优先，所以先考虑怎么划能让段数最小。

对于全部都是一个字母的，显然只能一个个划，所以段数即为长度，方案只有一种。

对于本身就是好字符串的，显然不需要划，所以段数即为 $1$，方案也只有一种。

剩下的情况，显然这个字符串 $s$ 可以被写成一个循环重复 $k$ 次（$2\le k \le |s|$），所以其每种字符的出现次数一定为 $k$ 的倍数，那么只要把最后一个划出来，不论是什么，那种字符的数量都一定不再是 $k$ 的倍数，所以一定只要划分成两个字符串就可以了。

考虑求方案数，枚举划分的位置并判断前后缀是否能被写成循环。

对于一个能被写成循环的字符串（不妨假设为 $A \dots A$，其中有 $k$ 个 $A$），显然它的 border 为$A\dots A$（其中有 $k-1$ 个 $A$）。那么它的长度一定为 $(k-1)\times|A|$，而这是显然能被 $|A|$ 整除的，所以只要判断能否整除即可。

既然提到了 border，那么用 KMP 就是十分自然的想法了，我们对原字符串求一下 $nxt$ 数组，再对翻转之后的字符串求一次 $nxt$ 数组就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
int nxt[5000000];
int bac[5000000];
int main(){
	string s;
	cin>>s;
	int n=s.size();
	s="#"+s;
	int j=0;
	nxt[1]=0;
	for(int i=2;i<=n;i++){
		while(j && s[i]!=s[j+1]){
			j=nxt[j];
		}
		if(s[i]==s[j+1]){
			j++;
		}
		nxt[i]=j;
	}
	if(nxt[n]==n-1){
		cout<<n<<"\n"<<1;
		return 0;
	}
	if(nxt[n]==0 || nxt[n]%(n-nxt[n])!=0){
		cout<<1<<"\n"<<1;
		return 0;
	}
	cout<<2<<"\n";
	s=s.substr(1);
	reverse(s.begin(),s.end());
	s="#"+s;
	bac[1]=0;
	for(int i=2,j=0;i<=n;i++){
		while(j && s[i]!=s[j+1]){
			j=bac[j];
		}
		if(s[i]==s[j+1]){
			j++;
		}
		bac[i]=j;
	}
	int ans=0;
	for(int i=1;i<n;i++){
		if((nxt[i]==0 || nxt[i]%(i-nxt[i])!=0) && (bac[n-i]==0 || bac[n-i]%(n-i-bac[n-i])!=0)){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

这题有紫吗？我场上直接一眼了，也就一个关键性质。

这题主要就是这个最重要的性质：对于一个字符串，如果它是由相同的字符构成的，则最小项数为它的长度，构造方法只有一种；如果它本身就是好字符串，则最小项数就是 $1$，构造方法也只有一种；否则最小项数为 $2$。

然后我就想复杂了，去用了各种玄学方法去求方案数然后浪费了 $10$ 分钟。

其实在确定最小项数为 $2$ 后，直接用 kmp 正反扫一遍看看前后缀串是不是好字符串。排除不是的即可。

真的没有紫。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
char s[N],s1[N];int pre[N],pre1[N];
signed main()
{
	scanf("%s",s+1);
	int len=strlen(s+1),res=0;
	for(int i=1;i<=len;i++)s1[len-i+1]=s[i];
    memset(pre,0,sizeof(pre));
    for(int i=1,j=pre[i];i<len;i++,j=pre[i])
    {
        while(j>0&&s[i+1]!=s[j+1])j=pre[j];
        if(s[i+1]==s[j+1])pre[i+1]=j+1;
    }
    for(int i=1,j=pre1[i];i<len;i++,j=pre1[i])
    {
        while(j>0&&s1[i+1]!=s1[j+1])j=pre1[j];
        if(s1[i+1]==s1[j+1])pre1[i+1]=j+1;
    }
    if(len%(len-pre[len])==0)res=len/(len-pre[len]);
    else res=1;
	if(res==len)
	{
		cout<<len<<'\n';
		cout<<1<<'\n';
		return 0;
	}
	else if(res==1)
	{
		cout<<1<<'\n'<<1<<'\n';
		return 0;
	}
	cout<<2<<'\n';
	int ans=len-1;
	for(int i=1;i<len;i++)
		if((i!=1&&i%(i-pre[i])==0&&i/(i-pre[i])!=1)||(i!=len-1&&(len-i)%((len-i)-pre1[len-i])==0&&(len-i)/((len-i)-pre1[len-i])!=1))
			ans--;
	cout<<ans;
	return 0;
}