题意：给定n(n≤10)个数，要求将它化为混偱环小数的形式，即前k个数不参与循环，之后所有数以p为循环节长度进行循环。求k和p，要求k+p尽量小，k+p相等时要求p尽量小。
样例1
输入：
6
612534 3157 423 3157 423 3157
输出：
1 2
样例2
输入：
9
1 2 1 3 1 2 1 3 1
输出：
0 4
分析：想了两个晚上，没有想到有什么数据结构可以支持这种操作，想要二分答案又不满足单调性，于是去请教TJW，TJW一语点醒梦中人：（还是log n的？，不大清楚）。那么直接暴力枚举p，然后均摊O(ln n)验证一下即可。以上是TJW的原话，具体细节还要处理一下：比如如何O(1)比对两段数？哈希即可，具体写法是设一个base数组，base[i]表示哈希常数key的i次方，再开一个hash数组，hash[i]表示前i位的哈希值，具体构造方法是，hash[i]=hash[i-1]*key。然后求l-r的hash值时只要求hash[r]-hash[l-1]*base[r-l+1]。除此以外，还有一个问题：循环节的开头（结尾）不一定是完整的，如何用较小的复杂度计算这段不完整的开头的长度？如果直接一个一个判断，整体复杂度就退化为O(n^2)了。这里我的解决方法是二分（刚好满足单调性），整体复杂度大概是O(nlogn + nlnn)。
/* Gym 101667I Slot Machines
1st Edition:2018.1.13 Saturday
Algorithm:Simulation
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cctype>
using namespace std; #define is_lower(c) (c>='a' && c<='z')
#define is_upper(c) (c>='A' && c<='Z')
#define is_alpha(c) (is_lower(c) || is_upper(c))
#define is_digit(c) (c>='0' && c<='9')
#define stop system("PAUSE")
#define ForG(a,b,c) for(int (a)=c.head[b];(a);(a)=c.E[a].nxt)
#define For(a,b,c) for(int (a)=(b);(a)<=(c);++a)
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define shl(x,y) ((x)<<(y))
#define shr(x,y) ((x)>>(y))
#define mp make_pair
#define pb push_back
#ifdef ONLINE_JUDGE
#define hash rename_hash
#define next rename_next
#define prev rename_prev
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef double db;
const ll inf=2000000007LL;
const double EPS=1e-;
const ll inf_ll=(ll)1e18;
const ll maxn=1000005LL;
const ll mod=1000000007LL; int n;
int a[maxn]; ull base[maxn];
ull hash[maxn];
const ll hash_base=; inline ull get_hash(int l,int r){
return (hash[r]-hash[l-]*base[r-l+]);
} int main(){
scanf("%d",&n);
base[]=;
For(i,,n) base[i]=base[i-]*hash_base;
For(i,,n){
scanf("%d",a+i);
hash[i]=hash[i-]*hash_base+a[i];
}
/*
For(i,1,n) printf("%llu ",hash[i]);
puts("");
*/
int ansk=inf>>,ansp=inf>>;
For(i,,n){
int pos=n;
ull nhash=get_hash(n-i+,n);
while(pos-i>=){
if(get_hash(pos-i+,pos)!=nhash) break;
pos-=i;
}
int l=,r=i+,mid,res=;
while(l<r){
mid=(l+r)>>;
if(pos-mid+<= || get_hash(pos-mid+,pos)!=get_hash(n-mid+,n)) r=mid;
else{l=mid+;res=mid;}
}
pos-=res;
if(i+pos<ansk+ansp){
ansk=pos;
ansp=i;
}
// printf("%d %d\n",pos,i);
}
printf("%d %d\n",ansk,ansp);
return ;
} /*
6
1 2 3 4 3 4 6
1 2 3 4 5 6 6
1 2 3 4 1 29 6
612534 3157 423 3157 423 3157 9
1 2 1 3 1 2 1 3 1 */
细节还要看代码
UPD.调和级数O(ln n) QwQ