P9187 [USACO23OPEN] Field Day S
普通的名字
·
·
题解
这里提供一个不同的思路。
首先把每个字符串压缩成一个数。数的范围显然是 [0,2^C)，记第 i 个字符串对应的数为 a_i。
对于第 i 个询问，答案等于 \max\limits_{j\in[1,N]}\operatorname{popcount}(a_i\oplus a_j)
如果暴力做，时间复杂度是 O(N^2) 的，不能通过。
换一个思路，从大到小枚举答案 x，判断是否可行。若存在 y\in[0,2^C),j\in[1,N]，使得 \operatorname{popcount}(y)=x，且 y\oplus a_j=a_i，就是可行的。
观察关键条件：y\oplus a_j=a_i，这让我们联想到 \text{FWT}。
将 a 中的各个元素丢进桶 t 里面，对于所有 j\in[0,2^C)，按照二进制 1 的个数归类，也按照类丢进桶里。然后对于每个类与 t 进行 \text{FWT}。在判断时，只需要判断下标 a_i 的数是否大于 0 即可。
时间复杂度为 O(C^2\cdot2^C)
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int C=18,N=1e5+1;
int c,n;
char s[C];
ll a[N],t[1<<C],b[C+1][1<<C],cnt[1<<C];
void fwt_xor(ll a[],int fl)
{
int n=1<<c;
for(int i=2;i<=n;i<<=1){
for(int j=0;j<n;j+=i){
for(int k=j;k<j+i/2;k++){
ll x=a[k]+a[k+i/2],y=a[k]-a[k+i/2];
a[k]=x>>(fl==-1),a[k+i/2]=y>>(fl==-1);
}
}
}
}
int main()
{
scanf("%d%d",&c,&n);
for(int i=0;i<(1<<c);i++) cnt[i]=cnt[i>>1]+(i&1),b[cnt[i]][i]=1;
for(int i=1;i<=n;i++){
scanf("%s",s);
for(int j=0;j<c;j++) a[i]=(a[i]<<1)|(s[j]=='G');
t[a[i]]++;
}
fwt_xor(t,1);
for(int i=0;i<=c;i++){
fwt_xor(b[i],1);
for(int j=0;j<(1<<c);j++) b[i][j]=b[i][j]*t[j];
fwt_xor(b[i],-1);
}
for(int i=1;i<=n;i++){
for(int j=c;j>=0;j--){
if(b[j][a[i]]){
printf("%d\n",j);
break;
}
}
}
}
```