囧== 下面的做法是错误的。下午在路上突然明白了==
哎，到现在还是只知道暴力的做法，囧爆了：http://www.cnblogs.com/liuxueyang/p/3322197.html
类似于前序和的那种思想。
b数组代表前序或，c数组代表后序或。
O(N)预处理出数组b和数组c
在从前往后扫一遍O(N)的复杂度，求出ans
如图：
可以发现c[Head] & b[Tail] 就可以求出任意区间内的f(Head, Tail)，可以知道，整个数组里面每个元素进入区间一次，出去一次，所以是O(N)的复杂度。
就这么欢乐地解决了==
#include <cstdio>
#include <cstring>
+;
int a[N], b[N], c[N];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int t; scanf("%d", &t);
; i <= t; ++i)
{
printf("Case #%d: ", i);
int j, n, m; scanf("%d%d", &n, &m);
memset(b, , sizeof(b));
memset(c, , sizeof(c));
;
; j <= n; ++j) {
scanf("%d", a+j);
b[j] = b[j-] | a[j];
}
; --j) {
c[j] = c[j+] | a[j];
}
, Tail = ;
while (Head <= n && Tail <= n) {
int tmp = c[Head] & b[Tail];
while (tmp < m && Tail <= n) {
ans++; tmp = c[Head] & b[++Tail];
}
++Head; Tail = Head;
}
printf("%I64d\n", ans);
}
;
}
其实正确的做法应该是这样的：
#include <cstdio>
#include <cstring>
typedef long long int LL;
+;
], cnt[];
int main(void) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int t; scanf("%d", &t);
memset(dig, , sizeof(dig));
dig[] = ;
; i <= ; ++i) dig[i] = dig[i-] * ;
; i <= t; ++i) {
printf("Case #%d: ", i);
, Tail = , n, m, j, k;
scanf("%d%d", &n, &m);
LL sum = (LL)n * (n+) / , tmp, nosum = ;
memset(cnt, , sizeof(cnt));
; j < n; scanf("%d", a+j++));
while (Tail < n) {
tmp = ;
; j <= ; ++j)
if (dig[j] & a[Tail])
++cnt[j];
; j <= ; ++j)
if (cnt[j])
tmp += dig[j];
if (tmp >= m) {
k = Head;
while (tmp >= m) {
tmp = ;
; j <= ; ++j)
if (dig[j] & a[Head])
--cnt[j];
; j <= ; ++j)
if (cnt[j])
tmp += dig[j];
++Head;
}
nosum += (LL)(n - Tail) * (Head - k);
}
++Tail;
}
printf("%I64d\n", sum - nosum);
}
;
}
一定要记得强制类型转换！！！18行的那种。纠结了一晚上==
嗨，中村。