### 概念

$$C_k=\sum_{i\oplus j=k}a_i\times b_j$$

### 原理

$$tf(C)=tf(A)\times tf(B)$$

#### xor

\begin{aligned} tf(A)&= (tf(A_0)+tf(A_1),tf(A_0)-tf(A_1)) \\ utf(A)&= (utf(\frac{A_0+A_1}{2}),utf(\frac{A_0-A_1}{2}))\end{aligned}

#### and

\begin{aligned}tf(A)&=(tf({A}{0})+tf({A}{1}),tf({A}{1})) \\ utf(A)&=(utf({A}{0})-utf({A}{1}),utf({A}{1}))\end{aligned}

#### or

\begin{aligned}tf(A)&=(tf({A}{0}),tf({A}{1})+tf({A}{0})) \\ utf(A)&=(utf({A}{0}),utf({A}{1})-utf({A}{0})) \end{aligned}

### 例题

#### 代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define maxn 2000005
#define md 10007
#define inv2 ((md+1)>>1)
using namespace std;
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
int n,f[maxn],g[25][maxn],w,s,bit;
void FWT(int *a,int l,int r){
if (l==r) return;
FWT(a,l,mid);FWT(a,mid+1,r);
int len=mid-l+1;
for (int i=l;i<=mid;++i){
int u=a[i],v=a[i+len];
a[i]=(u+v)%md;
a[i+len]=(u-v)%md;
}
}
void IFWT(int *a,int l,int r){
if (l==r) return;
int len=mid-l+1;
for (int i=l;i<=mid;++i){
int u=a[i],v=a[i+len];
a[i]=(u+v)*inv2%md;
a[i+len]=(u-v)*inv2%md;
}
IFWT(a,l,mid);IFWT(a,mid+1,r);
}
int main(){
freopen("sub.in","r",stdin);
freopen("sub.out","w",stdout);
for (int i=1;i<=n;++i){
f[x]=1,w^=x;
}
for (s=2,bit=1;s<2*n;s<<=1,bit++);
if (!w){printf("%d\n",n);return 0;}
f[0]=1;FWT(f,0,s-1);
for (int i=0;i<s;++i)
g[0][i]=1;
for (int j=1;j<=bit;++j)
for (int i=0;i<s;++i)
g[j][i]=g[j-1][i]*f[i]%md;
int l=0,r=bit+1;
while(l<r){
IFWT(g[mid],0,s-1);
if (g[mid][w]) r=mid;
else l=mid+1;
}
if (l==bit+1) puts("0");
else printf("%d\n",n-l);
}