【gym102222K】Vertex Covers（高维前缀和，meet in the middle）

题意：给定一张n点m边的图，点带点权，定义点覆盖的权值为点权之积，问所有点覆盖的权值之和膜q

n<=36， 1<=a[i]<=1e9，1e8<=q<=1e9

思路：n<=36，考虑middle in the middle分成两个点数接近的点集L和R

对于L，枚举其子集S，判断S能否覆盖所有L内部的边，预处理出所有合法的S的超集的贡献

对于R，枚举其子集T，判断T能否覆盖所有R内部的边，如果可以则可以推出L，R之间在确定R中选T的前提下左边至少需要选点集T’，答案即为T的点权之积*T’的超集的点权积之和

对于判断覆盖和根据T推T'使用了大量位运算加速

需要注意的是如果二进制左右移位可能超边界则要使用ull

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 //typedef pair<ll,ll>P;

 #define N  300010

 #define M  2000010

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 const //ll MOD=1e9+7,inv2=(MOD+1)/2;

       double eps=1e-;

       int INF=1e9;

       int dx[]={-,,,};

       int dy[]={,,-,};

       ull s[M];

       ll a[N],f[N];

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 int isok1(int S,int l,int r)

 {

     rep(i,l,r)

      if(!(S>>i&))

      {

          ull now=((s[i]<<(-r))>>(-r));

          if((now&S)!=now) return ;

      }

      return ;

 }

 int isok2(int S,int l,int r,int mid)

 {

     rep(i,l,r)

      if(!(S>>i&))

      {

         ll now=(s[i+mid]>>mid);

         if((now&S)!=now) return ;

      }

      return ;

 }

 int main()

 {

     int cas=read();

     rep(v,,cas)

     {

         int n=read(),m=read();

         ll MOD;

         scanf("%I64d",&MOD);

         int mid=n/;

         rep(i,,n-) scanf("%I64d",&a[i]);

         mem(s,);

         rep(i,,m)

         {

             int x=read(),y=read();

             x--; y--;

             s[x]|=1ll<<y;

             s[y]|=1ll<<x;

         }

         int S1=(<<mid)-;

         rep(i,,S1) f[i]=;

         rep(i,,S1)

         {

             ll t=;

             rep(j,,mid-)

              if(i>>j&) t=t*a[j]%MOD;

             if(isok1(i,,mid-)) f[i]=t;

         }

         rep(i,,mid-)

          rep(j,,S1)

           if(!(j>>i&)) f[j]=(f[j]+f[j^(<<i)])%MOD;

         int S2=(<<(n-mid))-;

         ll ans=;

         rep(i,,S2)

         {

             ll t=;

             rep(j,,n-mid-)

              if(i>>j&) t=t*a[j+mid]%MOD;

             if(isok2(i,,n-mid-,mid))

             {

                 ll base=;

                 rep(j,,mid-)

                 {

                     ull now=(s[j]>>mid);

                     if((now&i)!=now) base|=<<j;

                 }

                 ans=(ans+t*f[base]%MOD)%MOD;

             }

         }

         printf("Case #%d: ",v);

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

【gym102222K】Vertex Covers（高维前缀和，meet in the middle）

最新文章

热门文章