题目
题解
20分实在想不到是什么做法……
40分做法，从小到大枚举最小循环节长度，O(n) check即可，总复杂度O(n^2).
100分做法：
看到数据范围，T*n<=10^6，可知这题需要O(T*n)的做法。又因为是周期串，所以想到KMP算法。
记f[i]表示KMP中的next数组，则答案为n-f[n]。
简单解释：
设循环节为1~a，最后一个循环节的长度为b，丝中共有k个循环节。
则丝可以表示为123...a,123...a,123...a,...,123...b。其中共(k-1)个1~a和1个1~b。
利用反证法可以证明此时的f[n]=n-b-(a-b)=n-a。(从第一个1~a到第(k-1)个1~b，和第2个1~a到第k个1~b）
故答案为n-f[n]。
代码
#include <stdio.h>
#define N 1000010
int n,d[N],f[N];
inline void rd(int *n) {//快速读入
*n=;char c=getchar();
while(c<||c>) c=getchar();
while(c>&&c<) *n=(*n<<)+(*n<<)+(c^),c=getchar();
}
void solve() {
rd(&n);
for(int i=;i<n;++i) rd(d+i);
f[]=f[]=;
for(int i=,j;i<n;++i) {
j=f[i];
while(j&&d[i]!=d[j]) j=f[j];
f[i+]=d[i]==d[j]?j+:;
}//kmp求next数组
printf("%d\n",n-f[n]);
}
int main() {
int T;rd(&T);
while(T--) solve();
return ;
}