BZOJ 2081 [Poi2010]Beads

题目大意

给你一个串，让你从头开始每K个元素切一刀，最后如果有剩余就扔掉。问最多的不同子串的个数并输出方案。

这题一看就是Hash(qwq

这题建立两种Hash值：从前向后和从后向前两种。求出每个K下的子串个数，找最大就好了，时间复杂度$O(NlogN)$

注意** 这题卡Hash! 这题卡Hash! 这题卡Hash! **最终使用双模数双底数的高强度哈希过的，写到崩溃qwq

#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
#define moa 100000007
#define mob 1000000007
int n,a[200010],ans,ret[200010];
long long hsax[200010],hsay[200010],hsbx[200010],hsby[200010],bsa[200010],bsb[200010];
set<pair<long long,long long> >s;
int main()
{
    scanf("%d",&n);
    bsa[0]=bsb[0]=1;
    for(int i=1;i<=n;++i) bsa[i]=(bsa[i-1]*131)%moa,bsb[i]=(bsb[i-1]*233)%mob;
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    for(int i=1;i<=n;++i) hsax[i]=(hsax[i-1]*131+a[i])%moa,hsbx[i]=(hsbx[i-1]*233+a[i])%mob;
    for(int i=n;i;i--)    hsay[i]=(hsay[i+1]*131+a[i])%moa,hsby[i]=(hsby[i+1]*233+a[i])%mob;
    for(int i=1;i<=n;++i)
    {
        s.clear();
        for(int j=i;j<=n;j+=i)
        {
            long long ta=(hsax[j]+moa-(hsax[j-i]*bsa[i])%moa)%moa;
            ta=(ta*(hsay[j-i+1]+moa-(hsay[j+1]*bsa[i])%moa)%moa)%moa;
            long long tb=(hsbx[j]+mob-(hsbx[j-i]*bsb[i])%mob)%mob;
            tb=(tb*(hsby[j-i+1]+mob-(hsby[j+1]*bsb[i])%mob)%mob)%mob;
            s.insert(make_pair(ta,tb));
        }
        if(s.size()>ans)
        {
            ans=s.size();
            ret[ret[0]=1]=i;
        }
        else if(s.size()==ans) ret[++ret[0]]=i;
    }
    printf("%d %d\n",ans,ret[0]);
    for(int i=1;i<=ret[0];++i) printf("%d%c",ret[i],i==ret[0]?'\n':' ');
}