BZOJ 2801 Poi2010 Beads Hash

题目大意:给定1个数字串,求所有的k满足当将这个数字串从左到右分成大小为k的块时不同的块数量最多 反转同构算1种

枚举k,对每一个k将不同的串插入哈希表去重

反转同构啥的每一个串的哈希值乘1下反串的哈希值就好了

时间复杂度O(n/1+n/2+…+n/n)=O(nlogn)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 200200
#define BASE 200191
#define MOD 999911657
using namespace std;
int n,ans,a[M];
long long hash1[M],hash2[M],power[M];
int stack[M],top;
namespace Hash_Table{
struct List{
int hash_value;
bool flag;
List *next;
List(int _,List *__):
hash_value(_),flag(false),next(__) {}
}*head[BASE];
int tim[BASE],T;
void Initialize()
{
++T;
}
bool& Hash(int hash)
{
int pos=hash%BASE;
if(tim[pos]!=T)
tim[pos]=T,head[pos]=0x0;
for(List *temp=head[pos];temp;temp=temp->next)
if(temp->hash_value==hash)
return temp->flag;
return (head[pos]=new List(hash,head[pos]))->flag;
}
}
int main()
{
using namespace Hash_Table;
int i,j;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
hash1[i]=(hash1[i⑴]*BASE+a[i])%MOD;
for(i=n;i;i–)
hash2[i]=(hash2[i+1]*BASE+a[i])%MOD;
for(power[0]=1,i=1;i<=n;i++)
power[i]=power[i⑴]*BASE%MOD;
for(i=1;i<=n;i++)
{
int cnt=0;
Initialize();
for(j=i;j<=n;j+=i)
{
int l=j-i+1,r=j;
long long _hash1=(hash1[r]-hash1[l⑴]*power[r-l+1]%MOD+MOD)%MOD;
long long _hash2=(hash2[l]-hash2[r+1]*power[r-l+1]%MOD+MOD)%MOD;
bool &flag=Hash(_hash1*_hash2%MOD);
if(!flag) ++cnt;
flag=1;
}
if(cnt>ans) ans=cnt,top=0;
if(cnt==ans) stack[++top]=i;
}
cout<<ans<<' '<<top<<endl;
for(i=1;i<=top;i++)
printf("%d%c",stack[i],"
"[i==top]);
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 2801 Poi2010 Beads Hash

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡