# 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;
{
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; 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()
{
bin = 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; 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