bzoj3812: theme dp + tolerance and exclusion

meaning of the title

Here is a digraph. How many strong connection subgraphs are there

Analysis

The classic counting problem. It's done for the second time

fs=2s−∑t⊆s,t≠∅2cnts−t×2ways(s−t,t)gtfs=2s−∑t⊆s,t≠∅2cnts−t×2ways(s−t,t)gt

First enumerate the points in the strong connection with degree 0, and then conduct tolerance and exclusion
gs=fs−∑t⊆s,t≠∅,u∈tftgs−tgs=fs−∑t⊆s,t≠∅,u∈tftgs−t

Let's briefly explain that if our graph is not strongly connected, then it must be a DAG graph after the reduction point

For a DAG graph, if two points u and v are all graphs with an entry of 0, then v will be counted once when enumerating to u, and u will be counted once when enumerating v, so the odd number is - 1, and the even number is + 1

For a strong Unicom component, we enumerate the strong Unicom components whose entry degree is 0 after the reduction point. (of course, there may also be strong Unicom components whose entry degree is 0 in s-t, so we need to exclude them.) then the odd number is - 1, and the even number is + 1

gsgs means that for the points in s set, they are divided into strong connection components, which is actually the tolerance and exclusion of appeal

When t=s, gsgs does not need to add fsfs, because at this time, the whole subset is strongly connected

Then there is the dp of O(3n)O(3n), which needs to be analyzed carefully

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
typedef long long ll;
const ll Mod = 1e9+7;
inline ll read()
{
  ll p=0; ll f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}
ll mp[16]; ll cnt[1<<16]; ll f[1<<16],g[1<<16],h[1<<16]; ll bin[16*16];
ll low_bit(ll x){return x&(-x);} ll w[1<<16]; vector<ll>v;
void upd(ll &x,ll y){x=(x+y+Mod)%Mod;}
int main()
{
  ll n = read(); ll m = read();
  bin[0] = 1; for(ll i=1;i<=n*n;i++) bin[i] = bin[i-1] * 2 % Mod;
  for(ll i=1;i<=m;i++){ll x = read(); ll y = read(); x--; y--; mp[x] |= bin[y];}
  for(ll i=0;i<bin[n];i++) cnt[i] = __builtin_popcount(i);
  for(ll i=1;i<bin[n];i++)
  {
    if(low_bit(i) == i){f[i] = 1; g[i] = -1; continue;}
    v.clear(); for(ll j=i;j;j=(j-1)&i) v.pb(j);
    for(ll j=0;j<n;j++) if(i&bin[j]) w[bin[j]] = cnt[mp[j] & i];
    w[0] = 0; for(ll j=v.size()-1;j>=0;j--) w[v[j]] = w[v[j]^low_bit(v[j])] + w[low_bit(v[j])];
    f[i] = bin[w[i]];
    for(ll j=1;j<v.size();j++) if(v[j] & low_bit(i)) upd(g[i],- f[v[j]] * g[i^v[j]] % Mod);
    // for(ll j=i;j;j=(j-1)&i) printf("%lld %lld %lld\n",i,j,g[j]);
    for(ll j=0;j<v.size();j++)
    {
      upd(f[i] , bin[w[i^v[j]]] * g[v[j]] % Mod);
      //printf("%lld %lld\n",i,v[j]);
    }
    upd(g[i],-f[i]);
    for(ll j=0;j<v.size();j++) w[v[j]] = 0;
  }
  return printf("%lld\n",f[bin[n]-1]),0;
}

Posted on Mon, 30 Mar 2020 08:45:06 -0700 by DepretioN