题
OwO http://acm.hdu.edu.cn/showproblem.php?pid=6059
解
由于每个数字最多是30位，枚举数字每一位考虑，
建一棵记录前缀（位的前缀，比如10拆成1010，那么就把1010从前往后插入这个字典树中）的字典树，
nxt记录其后继，gcnt记录这个节点添加的个数，ng代表不符合要减去的个数（后文会提到）
tol[i][j]代表第i位的j（j=0,1）当前数量
枚举Ak的每一位，对于Ak的第t位（记作Ak[t]）
1. 如果Ak[t]==1，那么对答案产生贡献的Ai[t]和Aj[t]必然为0，而且Ai[0]~Ai[t-1]必然和Ak[0]~Ak[t-1]对应相等。
记Ak[t]对应地节点为chil，与其同父亲的另一个节点为xchil
1) Ak[t]加入后，第一部分要的贡献为 (tree[xchil].gcnt-1)*tree[xchil].gcnt/2 ，这是显然的，就是Ai[0]~Ai[t-1]和Ak[0]~Ak[t-1]和Aj[0]~Aj[t-1]全都相等情况
2) 第二部分是 tree[xchil].gcnt*(tol[i][1-s[i]]-tree[xchil].gcnt)-tree[xchil].ng ，减号前面的是Ai[0]~Ai[t-1]和Ak[0]~Ak[t-1]相等，且Ak[0]~Ak[t-1]和Aj[0]~Aj[t-1]有所不同的积（这样算出来有不合法的），因为有不合法所以要减去不合法的部分也就是tree[xchi].ng
而tree[xchi].ng的维护的话，每次加入一个点，那么这个点必然会在当前节点产生 tol[i][s[i]]-tree[chil].gcnt 点不合法的贡献，（Ai[0]~Ai[t-1]和Ak[0]~Ak[t-1]不相等，Ak[0]~Ak[t-1]和Aj[0]~Aj[t-1]相等这种不合法的情况）
2. 如果Ak[i]==0的话，那么答案也类似可以得到
（思路来自队友DorMOUSENone（队友真是太强辣））
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int M=5e5+55;
const int N=33;
const int infn=30;
struct Node
{
int nxt[2],gcnt;
ll ng;
} tree[M*N];
int n,tnum;
ll ans;
int s[N],tol[N][2];
void insert()
{
int rt=0,i,j,chil,xchil;
for(i=infn-1;i>=0;i--)
{
if(tree[rt].nxt[s[i]]==0)
tree[rt].nxt[s[i]]=++tnum;
chil=tree[rt].nxt[s[i]]; //children for s[i]
xchil=tree[rt].nxt[1-s[i]]; //another children
if(xchil)
ans+=1ll*(tree[xchil].gcnt-1)*tree[xchil].gcnt/2+1ll*tree[xchil].gcnt*(tol[i][1-s[i]]-tree[xchil].gcnt)-tree[xchil].ng;
tree[chil].ng+=tol[i][s[i]]-tree[chil].gcnt;
tree[chil].gcnt++;
tol[i][s[i]]++;
rt=chil;
}
}
void init()
{
memset(tree,0,(n+4)*N*sizeof(Node));
memset(tol,0,sizeof(tol));
tnum=0;
ans=0;
}
void solve()
{
int i,j,now;
for(i=1;i<=n;i++)
{
scanf("%d",&now);
for(j=0;j<infn;j++)
{
s[j]=now&1;
now>>=1;
}
insert();
}
}
int main()
{
int T,now;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
init();
solve();
printf("%lld
",ans);
}
return 0;
}
/*
200
4
1 3 0 0
*/
327MS代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
namespace fastIO {
#define BUF_SIZE 100000
//fread -> read
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pend == p1) {
IOerror = 1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '
' || ch == '
' || ch == ' ';
}
inline void read(int &x) {
char ch;
while(blank(ch = nc()));
if(IOerror)
return;
for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
}
#undef BUF_SIZE
};
using namespace fastIO;
typedef long long ll;
const int M=5e5+55;
const int N=33;
const int infn=30;
struct Node
{
int nxt[2],gcnt;
int ng;
} tree[M*N];
int n,tnum;
ll ans;
int s[N],tol[N][2];
void insert()
{
int rt=0,i,j,chil,xchil;
for(i=infn-1;i>=0;i--)
{
if(tree[rt].nxt[s[i]]==0)
tree[rt].nxt[s[i]]=++tnum;
chil=tree[rt].nxt[s[i]];
xchil=tree[rt].nxt[1-s[i]];
if(xchil)
ans+=1ll*(tree[xchil].gcnt-1)*tree[xchil].gcnt/2+1ll*tree[xchil].gcnt*(tol[i][1-s[i]]-tree[xchil].gcnt)-tree[xchil].ng;
tree[chil].ng+=tol[i][s[i]]-tree[chil].gcnt;
tree[chil].gcnt++;
tol[i][s[i]]++;
rt=chil;
}
}
void init()
{
memset(tree,0,(n+4)*N*sizeof(Node));
memset(tol,0,sizeof(tol));
tnum=0;
ans=0;
}
void solve()
{
int i,j,now;
for(i=1;i<=n;i++)
{
read(now);
for(j=0;j<infn;j++)
{
s[j]=now&1;
now>>=1;
}
insert();
}
}
int main()
{
int T,now;
read(T);
while(T--)
{
read(n);
init();
solve();
printf("%lld
",ans);
}
return 0;
}