BZOJ 4750: 密码安全 January 1, 2017 ###Description 有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复杂程度。 ![aa.jpg][1] 的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对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 取模的值。 ###Sample Input 3 1 61 5 1 2 3 4 5 5 10187 17517 24636 19706 18756 ###Sample Output 3721 148 821283048 ###Solution 单调栈扫一遍得到以每个数为最大值的区间，然后按位记前缀xor和的前缀和，对每个数分别统计答案 ###Code ```c++ #include<bits/stdc++.h> #define P 1000000061 int s[100001],S[100001],l[100001],r[100001],G[100010],*C=G+9; int main() { int T;for(scanf("%d",&T);T--;) { int n,m=0,i,j,t,p,A=0; scanf("%d",&n);s[n]=2e9; for(i=0;i<n;i++)scanf("%d",s+i); for(i=0;i<=n;i++) { while(m&&s[i]>=s[S[m-1]])r[S[--m]]=i-1; l[i]=m?S[m-1]+1:0,S[m++]=i; } for(j=0;j<30;j++) { for(i=t=p=0;i<n;i++)C[i]=t+=p^=s[i]>>j&1; for(i=0;i<n;i++) { t=C[i-1]-C[l[i]-2],p=C[r[i]]-C[i-1]; A=(((1ll*t*(r[i]-i+1-p)+1ll*p*(i-l[i]+1-t))%P<<j)%P*s[i]+A)%P; } } printf("%d\n",A); } } ``` [1]: /usr/uploads/2017/01/1896004125.jpg