Vertex Covers（高维前缀和）

Vertex Covers

时间限制: 5 Sec 内存限制: 128 MB
提交: 5 解决: 3

题目描述

In graph theory, a vertex cover of a graph G is a set of vertices S such that each edge of the graph is incident to at least one vertex of the set. That is to say, for every edge (u,v) of the graph, either u or v is in the vertex cover S.
Now, Kamilah shows you an undirected graph G without loops or multiple edges, each vertex of which has a weight.She can evaluate a vertex cover S of G by the product of weights of all vertices belonging to S.Here, the product of an empty set (of numbers) is defined as 1.
You are asked to calculate the sum of the evaluations described above for all vertex covers of G.

输入

The input contains several test cases, and the first line is a positive integer T indicating the number of test cases which is up to 3600.
For each test case, the first line contains three integers n (1≤n≤36) and m (0≤m≤n(n − 1)/2) which are the number of vertices and the number of edges in the graph G, and q (108≤q≤109 ) which is a prime number for the output.
The second line contains n integers, the i-th of which is the weight of the i-th vertices in G. All weights are in the range of 1 to 109 .
Each of the following m lines contains two integers u and v (1≤u, v≤n) describing an edge between the u-th vertex and the v-th one.
We guarantee that no more than 36 test cases satisfy n > 18.

输出

For each test case, output a line containing Case #x: y, where x is the test case number starting from 1, and y is the remainder of the answer divided by q.

样例输入

2
4 3 998244353
1 1 1 1
1 2
2 3
3 4
4 6 998244353
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4

样例输出

Case #1: 8
Case #2: 5

题意：设一个图的点覆盖的贡献是该点覆集中点权的积，求一个图的所有点覆盖的贡献和。
思路（来自题解）：

考虑折半，将点集分为大小接近的两部分 L 和 R，那么边集分为 L 内部的、R 内部的以及 L 和 R 之间的。
枚举 L 的子集 S，检查是否 L 内部所有边都被覆盖。
再枚举 R 的子集 T，检查是否 R 内部所有边都被覆盖，如果是，那么根据 L 和 R 之间的未覆盖边可以知道 L 的一个合法的子集 T′ 必须要覆盖掉当前的未覆盖边，那么可以在 L 内选出所有包含 T′ 的可行 S，这样 S+T 就是一个 vertex cover。
由于乘法满足分配率，只需要对 S 做一个高维前缀和就能快速计算答案。

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
 
const int N = 37;
long long arr[N];
long long pre[1<<20]={0};
 
unsigned long long Map[N]={0};
 
int check(int x,int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        if(((1<<i)&x)==0)
        {
            unsigned long long now=((Map[i]<<(63-r))>>(63-r));
            if((now&x)!=now)return 0;
        }
    }
    return 1;   
}
 
int check2(int x,int l,int r,int mid)
{
    for(int i=l;i<=r;i++)
    {
        if(((1<<i)&x)==0)
        {
            long long now=(Map[i+mid]>>mid);
            if((now&x)!=now)return 0;
        }
    }
    return 1;   
}
 
int main()
{
    int  t,Ca=1;
    scanf("%d",&t);
     
    while(t--)
    {
        int n,m;
        long long mod; 
        scanf("%d %d %lld",&n,&m,&mod);
         
        for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
         
        memset(Map,0,sizeof(Map));
        while(m--)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            u--;
            v--;
            Map[u]|=1ll<<v;
            Map[v]|=1ll<<u;
        }       
         
        int mid=n/2;
         
        for(int i=(1<<mid)-1;i>=0;i--)pre[i]=0;
         
        int upper=(1<<mid)-1;
         
        for(int i=0;i<=upper;i++)
        {
            long long sum=1;
            for(int j=0;j<mid;j++)
            if((1<<j)&i)sum=(sum*arr[j])%mod;
            
            if(check(i,0,mid-1))pre[i]=sum;
        }
         
        for(int i=0;i<mid;i++)   //高维后缀和 
        for(int j=upper;j>=0;j--)
            if((j&(1<<i))==0) pre[j]=(pre[j]+pre[j^(1<<i)])%mod;
         
        upper=(1<<(n-mid))-1;
         
        long long ans=0; 
        for(int i=0;i<=upper;i++)
        {
            long long sum=1;
            for(int j=0;j<n-mid;j++)
            if((1<<j)&i)sum=(sum*arr[j+mid])%mod;
             
            if(check2(i,0,n-mid-1,mid))
            {
                long long base=0;
                for(int x=0;x<=mid-1;x++)
                {
                    unsigned long long now=(Map[x]>>mid); 
                    if((now&i)!=now)base|=1<<x;
                }
                ans=(ans+sum*pre[base]%mod)%mod;
            } 
        }
        printf("Case #%d: %lld
",Ca++,ans);
    }
    return 0;
}

View Code