首页 > 代码库 > bzoj4750: 密码安全
bzoj4750: 密码安全
Description
有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个
人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络
中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安
全的影响，我们需要计算上述序列的复杂程度。
的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对10^9+61 取模的值即可。
Input
第一行包含一个正整数 T ，表示有 T 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行包含一个正整数 n 。
第二行包含 n 个非负整数，表示 A_1,A_2,?,A_n 。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
100% 的数据满足：1≤T≤200,1≤n≤10^5,1≤∑n≤10^6,0≤A_i≤10^9
Output
对于每组数据输出一行，包含一个整数，表示答案对10^9+61 取模的值。
用单调栈预处理出每个a[x]作为最大值（值相同则比较位置）所出现的区间，具体形式是[l,r] | l in [ls[x],x], r in [x,rs[x]]，于是可以按位处理然后前缀和一下对每个a[x]分别计算贡献
#include<cstdio>typedef long long i64;const int N=100007,P=1000000061;char buf[15000007],*ptr=buf-1;int _(){ int x=0,f=1,c=*++ptr; while(c<48)c==‘-‘&&(f=-1),c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x*f;}int T,n,a[N],ls[N],rs[N],ss[N],sp=0,s[N],ans;int main(){ buf[fread(buf,1,sizeof(buf),stdin)]=0; for(T=_();T;--T){ n=_(); for(int i=1;i<=n;++i)a[i]=_(); for(int i=1;i<=n;++i){ while(sp&&a[ss[sp]]<a[i])rs[ss[sp--]]=i-1; ss[++sp]=i; } while(sp)rs[ss[sp--]]=n; for(int i=n;i;--i){ while(sp&&a[ss[sp]]<=a[i])ls[ss[sp--]]=i+1; ss[++sp]=i; } while(sp)ls[ss[sp--]]=1; ans=0; for(int i=0;i<30;++i){ int sum=0; for(int j=1;j<=n;++j)s[j+1]=s[j]^(a[j]>>i&1); for(int j=1;j<=n;++j)s[j+1]+=s[j]; for(int j=1,v1,v2;j<=n;++j){ v1=s[rs[j]+1]-s[j]; v2=s[j]-s[ls[j]-1]; sum=(sum+(i64(v1)*(j+1-ls[j]-v2)+i64(v2)*(rs[j]+1-j-v1))%P*a[j])%P; } ans=(ans+(i64(sum)<<i)%P)%P; } printf("%d\n",ans); } return 0;}
bzoj4750: 密码安全
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。