51Nod1824 染色游戏 【Lucas定理】【FMT】【位运算】

我的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 ;

 }