poj3261

题解：

同ｂｚｏｊ１７１７

代码：

#include<bits/stdc++.h>
using namespace std;
const int P1=1318275,P2=1324710,P=1718414;
int a1[P],num[P],a2[P],flag[P],a[P],inv1[P],inv2[P],n,m;
int find(int x,int y)
{
    int k=(long long)x*y%P;
    for (;flag[k]&&(a1[k]!=x||a2[k]!=y);k=(k+1)%P);
    return k;
}
int pd(int x)
{
    memset(a1,0,sizeof a1);
    memset(a2,0,sizeof a2);
    memset(flag,0,sizeof flag);
    memset(num,0,sizeof num);
    inv1[0]=inv2[0]=1;
    for (int i=1;i<=n;i++)inv1[i]=inv1[i-1]*233%P1,inv2[i]=inv2[i-1]*233%P2;
    int p1=0,p2=0;
    for (int i=1;i<=n;i++)
     {
         p1=(p1*233+a[i])%P1;
         p2=(p2*233+a[i])%P2;
         if (i>x)
          {
              p1=(p1-(long long)a[i-x]*inv1[x]%P1+P1)%P1;
              p2=(p2-(long long)a[i-x]*inv2[x]%P2+P2)%P2;
          }
         if (i<x)continue;
         int l=find(p1,p2);
         a1[l]=p1;a2[l]=p2;flag[l]=1;
         num[l]++;
         if (num[l]>=m)return 1;
     }
    return 0; 
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=n;
    while (l<r)
     {
         int mid=(l+r+1)/2;
         if (pd(mid))l=mid;
         else r=mid-1;
     }
    printf("%d
",l); 
}