我的FMT是在VFleaKing的论文中学到的。51Nod的评测机好恶心。
题目分析：
题目很明显是要你求一个类似卷积的式子。但是我们可以注意到前面具有组合数，如果拆成阶乘会很大，在模意义下你无法判断奇偶性。另辟蹊径，可以采用Lucas定理分析。
观察组合数的奇偶性，就会发现$\binom{n}{k} % 2 == 0$的充要条件是在模$2$意义下不存在$\binom{0}{1}$。这意味着$\binom{0}{0} \binom{1}{1} \binom{1}{0}$都是可以接受的。换句话说$k$是$n$的子集。注意到原来的是基础的卷积形式，所以我们要做的是对a和b的子集卷积。
全程在模$2$意义下进行，不难想到用二进制压位。
代码：
#include<bits/stdc++.h>
using namespace std; #define RI register int const int maxn = (<<)+; int n,m,len;
int a[maxn],b[maxn];
char buffer[], *buf=buffer; inline void in(int &x) {
while(*buf>'' || *buf<'') ++buf;
for(x=;*buf>=''&&*buf<=''; ++buf) x=x*+*buf-'';
} inline void in1(int &x){
while(*buf>'' || *buf<'') ++buf;
x = *buf-'';++buf;
} struct Bitset{
unsigned long long data[<<];
int PrintBit(int now){
int tm = now>>,im = now&;
return (bool)(data[tm]&(1ll<<im));
}
void reset(int start,int len){
int tm = start>>,im = start&;
if(len >= ){
int ww = len>>;
for(RI i=;i<ww;++i)data[tm+ww+i] ^= data[tm+i];
}else{
long long forw = (((1ll<<len)-)<<im);
forw = (forw&data[tm]);
forw <<= len; data[tm] ^= forw;
}
}
void SetBit(int now){
int tm = now>>,im = now&;
data[tm] |= (1ll<<im);
}
}am[],bm[],cm[]; int cnt[maxn];
int f1,f2; void read(){
in(n),in(m);
for(RI i=;i<=n;++i) in1(a[i]);
for(RI i=;i<=m;++i) in1(b[i]);
for(RI i=;i<=n;++i) a[i] &= ;
for(RI i=;i<=m;++i) b[i] &= ;
n = (n>m?n:m);m = ;len = ;
while(m <= n) m<<=,len++;
a[] = b[] = ;
} void FMT(int place,int st){
if(place == ){
for(RI i=;i<m;i<<=){
int jg = m/(i<<);
for(RI j=;j<m;j+=(jg<<))
am[st].reset(j,jg);
}
}else{
for(RI i=;i<m;i<<=){
int jg = m/(i<<);
for(RI j=;j<m;j+=(jg<<))
bm[st].reset(j,jg);
}
}
} void IFMT(int num){
for(RI i=;i<m;i<<=){
for(RI j=;j<m;j+=(i<<))
cm[num].reset(j,i);
}
} void work(){
for(RI i=;i<m;++i) { cnt[i] = cnt[i>>]+(i&); }
for(RI i=;i<=n;++i) {
if(a[i]) am[cnt[i]].SetBit(i);
if(b[i]) bm[cnt[i]].SetBit(i);
}
for(RI i=;i<=len;++i){ FMT(,i); FMT(,i); }
for(RI i=;i<m;++i){
f1 = ,f2 = ;
for(RI j=;j<=len;++j){
f1 += (am[j].PrintBit(i)<<j);
f2 += (bm[j].PrintBit(i)<<j);
}
int n1 = ,n2 = ;
for(RI j=;j<=len;++j){
n1 = n1+(f1&(<<j));
if(f2&(<<j)) n2 = (n2<<)+;
else n2 <<=;
if(cnt[n1&n2]&) cm[j].SetBit(i);
}
}
for(RI i=;i<=len;++i) IFMT(i);
long long ans = ;
for(RI i=;i<m;++i){
ans += 1ll*cm[cnt[i]].PrintBit(i)*i*i;
}
printf("%lld",ans);
} int main(){
fread(buffer, , (sizeof buffer)-, stdin);
read();
work();
return ;
}