题解：P10242 [THUSC 2021] Emiya 家明天的饭
inc1ude_c
·
·
题解
首先发现人很少，所以我们考虑菜对人而不是人对菜。设一个菜喜欢一个人当且仅当这个人喜欢这个菜。
设 p_i 为第 i 道菜喜欢的人的集合。
答案即为：
\max_S(\sum_{i\in S}\sum_{S\subseteq p_j}a_{i,j})
设 $f_{i,s}=\sum\limits_{p_j=s}a_{i,j}$。
答案为：
$$\max_S(\sum_{i\in S}\sum_{S\subseteq T}f_{i,T})$$
发现 $\sum_{S\subseteq T}f_{i,T}$ 就是且运算的 FWT。然后就做完了。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int N=22,NN=(1<<N)+10,M=1e6+10;
int n,m;
int a[N][M],p[M];
ll f[N][NN];
void FWT(ll *f,int len){
for(int mid=1;mid<len;mid<<=1){
for(int i=0;i<len;i+=(mid<<1)){
for(int j=0;j<mid;j++){
f[i+j]+=f[i+j+mid];
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n){
rep(j,1,m){
scanf("%d",&a[i][j]);
if(a[i][j]!=-1)p[j]|=(1<<(i-1));
}
}
rep(i,1,n){
rep(j,1,m){
f[i][p[j]]+=a[i][j];
}
FWT(f[i],1<<n);
}
ll ans=0;
rep(s,0,(1<<n)-1){
ll tans=0;
rep(i,1,n){
if(!(s&(1<<(i-1))))continue;
tans+=f[i][s];
}
ans=max(ans,tans);
}
printf("%lld",ans);
return 0;
}
```