51nod 1824 染色游戏

Description

Data Constraint

$1$≤$n$,$m$<$2^{20}$

Solution

首先对$r$和$b$都作模2操作。
首先有

$$f_x=\sum_{i=0}^xC_{x}^i r_i b_{x-i}\ mod \ 2$$
若 $f_x$等于 $1$则说明$f_x$将对答案贡献 $x^2$。
接着考虑 $C_{x}^i$在什么条件下满足 $C_{x}^i\ mod \ 2$= $1$。
我们可以通过$Lucas$定理或 $Krumer$定理推得它的充分必要条件为
$i\ or\ x=i$ (或者 $i\ and\ (x-i)=0$)
若 $x\ and\ y=0$，那么也一定会有 $x\ +\ y=x\ or \ y$

于是我们可以得到

$$f_{x\ or \ y}=\sum r_x b_{y}[x\ and\ y=0]\ mod \ 2$$
转换一下也就可以得到
$$f_{x\ or \ y}=\sum r_x b_{y}[bits(x)+bits(y)=bits(x+y)]\ mod \ 2$$
其中 $bits$( $x$)表示$x$在二进制下有多少位为 $1$。

这下就简单了，我们按照数的$bits$值分成 $log_{n+m}$组，每一组单独求一次 $FWT$，求或卷积的时候直接 $log^2_{n+m}$暴力枚举组和组之间的卷积在逆 $FWT$即可。

由于常数较大，做的时候需要卡卡常，比如说模$2$意义下的加减都可以看成异或（$FWT$的或卷积只有加减运算），同时需要压位，显然我们可以一段数一起异或，于是便把这一段数压成一个数再做$FWT$即可（当然，这段数的长度必须为$2$的幂次）。

时间复杂度为$O$($n$ $log_2^2$ n <script type="math/tex" id="MathJax-Element-313">n</script>)。

Code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)using namespace std;
typedef long long ll;
const ll N=22e5,M=23,K=2e5,ws=16,R=4,P=7e4,zd=65536;
int a[N],b[N],c[N],t[N],ans[N],c1[N],n,m,zg,bj,dq;
int f[M][K],g[M][K],bits[N],op[M],dy[65550];inline int read()
{int o=0; char ch=' ';for(;ch<'0'||ch>'9';ch=getchar());return ch-48;
}inline int fj(int o)
{int y=1,p=0;for(;y<=o;y<<=1,++p);return p;
}inline void tf_or(int *a)
{for(int m=2;m<=zg+1;m<<=1){int half=m>>1;for(int j=0;j<=zg;j+=m)fo(l,0,half-1)a[l+half+j]^=a[l+j];}
}inline void high_tf_or(int *a)
{int re=(zg+1)>>4;for(int m=2;m<=re;m<<=1){int half=m>>1;for(int j=0;j<re;j+=m)fo(l,0,half-1)a[(l^half)+j]^=a[l+j];}
}inline int bh(int oo)
{fd(i,15,0)op[i]=oo&1,oo>>=1;for(int m=2;m<=16;m<<=1){int half=m>>1;for(int j=0;j<16;j+=m)fo(l,0,half-1)op[l+j+half]^=op[l+j];}int y=0;fo(i,0,15)y=(y*2)+op[i];return y;
} int main()
{cin>>n>>m;fo(i,0,zd-1)if(!dy[i])dy[i]=bh(i),dy[dy[i]]=i;a[0]=b[0]=1;fo(i,1,n)a[i]=read(),a[i]&=1;fo(i,1,m)b[i]=read(),b[i]&=1;int len=fj(n+m);zg=(1<<len)-1; bj=len>8;if(bj)dq=zg>>R;else dq=zg;fo(i,0,zg)bits[i]=bits[i>>1]+(i&1);fo(l,0,len){fo(i,0,zg)if(bits[i]==l)c[i]=a[i];else c[i]=0;if(bj==0){tf_or(c);fo(i,0,zg)f[l][i]=c[i];}else{fo(i,0,dq){t[i]=0;fo(j,(i<<R),((i+1)<<R)-1)t[i]=(t[i]<<1)+c[j];}fo(i,0,dq)t[i]=dy[t[i]];high_tf_or(t);fo(i,0,dq)f[l][i]=t[i];}fo(i,0,zg)if(bits[i]==l)c[i]=b[i];else c[i]=0;if(bj==0){tf_or(c);fo(i,0,zg)g[l][i]=c[i];}else{fo(i,0,dq){t[i]=0;fo(j,(i<<R),((i+1)<<R)-1)t[i]=(t[i]<<1)+c[j];}fo(i,0,dq)t[i]=dy[t[i]];high_tf_or(t);fo(i,0,dq)g[l][i]=t[i];}}fo(l,0,len){fo(j,0,dq)t[j]=0;fo(i,0,l)fo(j,0,dq)t[j]^=f[i][j]&g[l-i][j];if(!bj){fo(j,0,dq)c[j]=t[j];tf_or(c);}else{fo(j,0,dq)t[j]=dy[t[j]];high_tf_or(t);fo(i,0,dq)fd(j,15,0)c[(i<<4)^j]=t[i]&1,t[i]>>=1;}fo(i,0,zg)if(bits[i]==l)ans[i]^=c[i];}ll answer=0;fo(i,1,zg)if(ans[i])answer=answer+(ll)i*((ll)i);printf("%lld",answer);
}