CodeChef - COVERING Covering Sets(sosdp)

链接

题面:

CodeChef - COVERING Covering Sets(sosdp)
定义:R(x)=x&(ijk)=xA[i]B[j]C[k]R(x)=\sum_{x\&(i|j|k)=x}A[i]*B[j]*C[k]R(x)=∑x&(i∣j∣k)=x​A[i]∗B[j]∗C[k]

题目就变成了x[0,2n)R(x)\sum_{x\in[0,2^{n})}R(x)∑x∈[0,2n)​R(x)


思路:

先用sosdp从前往后转移,求出A、B、C的状态,然后用一个dp数组存一下
dp[mask]=A[mask]B[mask]C[mask] (mod p)dp[mask]=A[mask]*B[mask]*C[mask]\ (mod\ p)dp[mask]=A[mask]∗B[mask]∗C[mask] (mod p)
但是会发现不太对的地方,如求dp[1111b]=A[1111b]B[1111b]C[1111b]dp[1111b]=A[1111b]*B[1111b]*C[1111b]dp[1111b]=A[1111b]∗B[1111b]∗C[1111b]
如果A中只有0001b,B中只有1000b,C中只有0100b
A[1111b]=x1111A[x]A[1111b]=\sum_{x\in1111的子集} A[x]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;
}
上一篇:leetcode(22)-字母异位词分组


下一篇:Redis介绍