[Str记录]AT2040 [ARC060D] 最良表現 / Best Representation

**题意** ： 若一个串不是整循环串，称之为好串。 给出一个字符串 $S$ 。 求出 $S$ 的“好串拆分”的最小段数。以及段数最小前提下的方案数（对 $10^9+7$ 取模）。 $S\leq 5\times 10^5$ ，时限$\texttt{2s}$。 ------------ 如果这不是个 ARC 题，咋一看确实挺唬人的…… - 若 $S$ 中只有一种字符，则只能拆分为 $|S|$ 段，每段一个字符。 - 若 $S$ 本身为好串，则保留本身。 接下来只需要考虑 $S$ 是整循环串的情况。 此时可以发现，最小段数一定是 $2$。 - **证明** ： - **结论** ：对于周期 $\geq 2$ 的整循环串 $S$ ，拿去最后一个字符后，一定不是整循环串。 于是，我们将 $S$ 切分为 $S_{1\sim|S|-1},S_{|S|}$ 即可构造两段的方案。 下面是结论的证明 ： 记 $S$ 的最小正循环节为 $p$ ，记 $S'=S_{1\sim|S|-1}$ ，且 $S'$ 的最小整循环节为 $q$。 由于 $|S|,|S|-1$ 之中必有一个是奇数，不难证明 $p+q\leq |S|-1$。 于是，根据弱周期引理，$\gcd(p,q)$ 是 $S'$ 的周期，显然，也是整周期。 由于 $q$ 是 $S'$ 的最小整周期，则必有 $\gcd(p,q)=q$。 我们知道 $p\big||S|,q\big|(|S|-1)$ ，故 $\gcd(|S|,|S|-1)\geq \gcd(p,q)=q$。 另一方面，显然有 $\gcd(|S|,|S|-1)=1$ ，故 $q=1$。 这说明 $S_{1\sim |S|-1}$ 都是同一个字符。由于整个串不都是同一个字符，故 $S_{|S|}$ 必然是不同的字符。 此时 $S$ 必然不是整循环串，矛盾。 然后我们只需要枚举每种切分，并判断每个 前/后 缀是否为正循环串即可。 - **结论** ： 对于整循环串 $S$ ，$S$ 的最小周期同时也是 $S$ 的最小整周期。 那么，我们使用 $\rm KMP$ 求出 $T$ 的每个 前/后 缀的最小周期，即可得知答案。 复杂度 $O(n)$。（模数是来开玩笑的啦） ```cpp #include<algorithm> #include<cstring> #include<cstdio> #define MaxN 500500 using namespace std; const int mod=1000000007; void kmp(char *s,int *f,int n) { for (int i=2,p=0;i<=n;i++){ while(p&&s[p+1]!=s[i])p=f[p]; if (s[p+1]==s[i])p++; f[i]=p; }for (int i=1;i<=n;i++)f[i]=i-f[i]; } int n,pl[MaxN],pr[MaxN]; char s[MaxN]; int main() { scanf("%s",s+1); n=strlen(s+1); kmp(s,pl,n); reverse(s+1,s+n+1); if (pl[n]==1){printf("%d\n1\n",n);return 0;} if (pl[n]==n||n%pl[n]){printf("1\n1");return 0;} kmp(s,pr,n); reverse(pr+1,pr+n+1); int cnt=0; for (int i=1;i<n;i++) cnt+=((i%pl[i]||pl[i]==i)&&((n-i)%pr[i+1]||pr[i+1]==n-i)); printf("2\n%d",cnt); return 0; } ```