题面:
定义:R(x)=∑x&(i∣j∣k)=xA[i]∗B[j]∗C[k]
题目就变成了∑x∈[0,2n)R(x)
思路:
先用sosdp从前往后转移,求出A、B、C的状态,然后用一个dp数组存一下
dp[mask]=A[mask]∗B[mask]∗C[mask] (mod p)
但是会发现不太对的地方,如求dp[1111b]=A[1111b]∗B[1111b]∗C[1111b]
如果A中只有0001b,B中只有1000b,C中只有0100b
A[1111b]=∑x∈1111的子集A[x],所以A[1111b]不为0,B和C同理。算出来的dp[1111b]不为0,与事实不符了,所以要减去一些东西,这些东西就是当前mask的真子集。避免后效性,需要从后往前做sosdp来减去来自真子集的贡献。
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mod=1e9+7;
ll pow_2[25];
ll A[1<<20],B[1<<20],C[1<<20],F[1<<20];
int count_of_one(int x){
int ret=0;
while (x){
if(x&1){
ret++;
}
x>>=1;
}
return ret;
}
int main(){
pow_2[0]=1ll;
for(int i=1;i<=20;i++){
pow_2[i]=pow_2[i-1]*2%mod;
}
int n;
scanf("%d",&n);
for(int i=0;i<(1<<n);i++){
scanf("%lld",&A[i]);
}
for(int i=0;i<(1<<n);i++){
scanf("%lld",&B[i]);
}
for(int i=0;i<(1<<n);i++){
scanf("%lld",&C[i]);
}
for(int i=0;i<=20;i++){
for(int j=0;j<1<<20;j++){
if(j>>i&1){
A[j]=(A[j]+A[j-(1<<i)])%mod;
B[j]=(B[j]+B[j-(1<<i)])%mod;
C[j]=(C[j]+C[j-(1<<i)])%mod;
}
}
}
for(int i=0;i<1<<20;i++){
F[i]=A[i]*B[i]%mod*C[i]%mod;
}
for(int i=20;i>=0;i--){
for(int j=0;j<1<<20;j++){
if(j>>i&1){
F[j]=(F[j]-F[j-(1<<i)]+mod)%mod;
}
}
}
ll ans=0;
for(int i=0;i<1<<20;i++){
ans=(ans+F[i]*pow_2[count_of_one(i)])%mod;
}
printf("%lld\n",ans);
return 0;
}