【JZOJ 4922】【NOIP2017提高组模拟12.17】环

Description

小A有一个环，环上有n个正整数。他有特殊的能力，能将环切成k段，每段包含一个或者多个数字。对于一个切分方案，小A将以如下方式计算优美程度：
首先对于每一段，求出他们的数字和。然后对于每段的和，求出他们的最大公约数，即为优美程度。
他想通过合理地使用他的特殊能力，使得切分方案的优美程度最大。

Data Constraint

对于20%的数据，n<=16,ai<=10
对于40%的数据，n<=100,ai<=1000
对于100%的数据，n<=2000,1<=ai<=50000000(5e7)

Solution

显然，将一段序列分成i段答案是不下降的。所以我们从大到小枚举总和sum的约数。对于每一个约数x，我们枚举一下序列的前缀和，若当前的前缀和 a1modx=k ,之前有一个前缀和也同样满足 a2modx=k ，那么a1和a2之间的数的和一定满足是x的倍数。所以我们将所有前缀和mod x后打入一个哈希表中，取一个出现次数最大的即可。总时间复杂度O( N3logN )。

Code

#include<iostream>
#include<math.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=4*1e6,maxn1=2005;
ll d[maxn],b[maxn],a[maxn1],f[maxn1],h[maxn],h1[maxn],h2[maxn];
ll n,i,t,j,k,l,x,y,sum,p;
ll hash(int x){
    int t=x%maxn;
    while (h[t] && h[t]!=x && h2[t]==p) t=(t+1)%maxn;
    if (h2[t]!=p) h1[t]=0;
    h[t]=x,h2[t]=p;
    return ++h1[t];
}
void pan(ll x){
    ll i,j,t,k,l;
    t=0;
    for (j=1;j<=n;j++)
        t=max(t,hash(f[j]%x));
    b[t]=max(b[t],x);
}
int main(){
    freopen("data.in","r",stdin);
    scanf("%lld",&n);
    for (i=1;i<=n;i++)
        scanf("%lld",&a[i]),x+=a[i],b[i]=1;
    sum=x;
    for (j=1;j<=n;j++)
        f[j]=f[j-1]+a[j];
    t=sqrt(x);
    for (i=1;i<=t;i++){
        if (x%i) continue;
        d[++d[0]]=i;b[d[0]]=x/i;
    }   
    for (i=d[0];i>=1;i--)
        d[++d[0]]=b[i],b[i]=1;
    j=d[0];
    for (j=d[0];j>=1;j--)
        p++,pan(d[j]);
    for (i=n-1;i>=1;i--)
        b[i]=max(b[i],b[i+1]);
    for (i=1;i<=n;i++)
        printf("%lld\n",b[i]);
}