题目
题解
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=0;char c=getchar(); while(c<48||c>57) c=getchar(); while(c>47&&c<58) *n=(*n<<3)+(*n<<1)+(c^48),c=getchar(); } void solve() { rd(&n); for(int i=0;i<n;++i) rd(d+i); f[0]=f[1]=0; for(int i=1,j;i<n;++i) { j=f[i]; while(j&&d[i]!=d[j]) j=f[j]; f[i+1]=d[i]==d[j]?j+1:0; }//kmp求next数组 printf("%d ",n-f[n]); } int main() { int T;rd(&T); while(T--) solve(); return 0; }