cjb-poi2010beads

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define N 210000
const int P=200011,D=1000173169;
int n,a[N],pow[N],f1[N],f2[N];
vector<int> ans[N];
int hash1(int l,int r)
{
    return (long long)((long long)f1[r]-(long long)f1[l-1]*pow[r-l+1]%D+D)%D; 
}
int hash2(int l,int r)
{
    return (long long)((long long)f2[l]-(long long)f2[r+1]*pow[r-l+1]%D+D)%D; 
}
int work(int k)
{
    set<int> q;
    for(int i=1;i*k<=n;i++)q.insert(min(hash1((i-1)*k+1,i*k),hash2((i-1)*k+1,i*k)));
    return q.size();
}
int main()
{
    cin>>n;
    rep(i,n)scanf("%d",&a[i]);
    pow[0]=1; rep(i,n)pow[i]=(long long)pow[i-1]*P%D;
    for(int i=1;i<=n;i++)f1[i]=(long long)((long long)f1[i-1]*P+a[i])%D;
    for(int i=n;i>=1;i--)f2[i]=(long long)((long long)f2[i+1]*P+a[i])%D;
    rep(i,n)ans[i].clear();
    rep(i,n)ans[work(i)].pb(i);
    for(int i=n;i>=1;i--)
        if (ans[i].size())
        {
            int cnt=ans[i].size();
            printf("%d %d\n",i,cnt);
            for(int j=0;j<cnt;j++)printf("%d%c",ans[i][j],j==cnt-1?'\n':' ');
            return 0;
        }
}

}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define N 210000
const int P=200011,D=1000173169;
int n,a[N],pow[N],f1[N],f2[N];
vector<int> ans[N];
int hash1(int l,int r)
{
    return (long long)((long long)f1[r]-(long long)f1[l-1]*pow[r-l+1]%D+D)%D; 
}
int hash2(int l,int r)
{
    return (long long)((long long)f2[l]-(long long)f2[r+1]*pow[r-l+1]%D+D)%D; 
}
int work(int k)
{
    set<int> q;
    for(int i=1;i*k<=n;i++)q.insert(min(hash1((i-1)*k+1,i*k),hash2((i-1)*k+1,i*k)));
    return q.size();
}
int main()
{
    cin>>n;
    rep(i,n)scanf("%d",&a[i]);
    pow[0]=1; rep(i,n)pow[i]=(long long)pow[i-1]*P%D;
    for(int i=1;i<=n;i++)f1[i]=(long long)((long long)f1[i-1]*P+a[i])%D;
    for(int i=n;i>=1;i--)f2[i]=(long long)((long long)f2[i+1]*P+a[i])%D;
    rep(i,n)ans[i].clear();
    rep(i,n)ans[work(i)].pb(i);
    for(int i=n;i>=1;i--)
        if (ans[i].size())
        {
            int cnt=ans[i].size();
            printf("%d %d\n",i,cnt);
            for(int j=0;j<cnt;j++)printf("%d%c",ans[i][j],j==cnt-1?'\n':' ');
            return 0;
        }
}