日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > php教程 > BZOJ 2801 Poi2010 Beads Hash

BZOJ 2801 Poi2010 Beads Hash

來源:程序員人生   發布時間:2015-03-19 08:27:53 閱讀次數:2421次

題目大意:給定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; }


生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 99免费视频 | 91免费看片网站 | 午夜男人的天堂 | 九一毛片 | 日韩精品视频免费 | 欧洲av一区二区 | 亚洲欧洲免费 | 一本黄色片 | 成人在线一区二区 | 精品视频久久久久久久 | 国产伦精品一区二区三区照片 | 好吊日精品视频 | 国产精品乱码久久久久久 | 日本久久久久久久久 | 18久久久久久 | 国产三级一区 | 国产精品无码久久久久 | 久久成人一区二区 | 亚洲精品免费观看 | 欧美性xxxxx| 精品一区在线播放 | 国产精品一区二区三区免费视频 | 99久久久久久久久久久 | 欧美日本片 | 国产精品爱啪在线线免费观看 | 国产一区二区欧美 | 国内久久| 久久久一区二区三区 | 激情五月激情综合网 | av青青 | 九九热av | 亚洲一区二区三区中文字幕 | 天天干天天插 | 亚洲一区二区三区中文字幕 | 日本色网址| 久久久精品亚洲 | 91精品国产自产91精品 | 成人在线视频免费 | 国产又色又爽又黄刺激视频免费 | 欧洲一区二区三区免费视频 | 国产精品久久久久久久久久久不卡 |