题解：P11714 [清华集训 2014] 主旋律

· · 题解

Solution

DAG 计数模板题。

考虑算出 dp_S 为，考虑 S 内部的边，有多少种方案使得它是强联通的。

设内部有 e 条边，那么显然要用 2^e 减去至少两个强联通分量的情况。

根据经典套路，对零度点进行容斥，容斥系数为 (-1)^{cnt}，其中 cnt 是你钦定的 0 度点（就是缩点之后的强联通分量）个数。

按照 cnt 奇偶性进行合并，你只需要在加入一个联通分量的时候乘 -1 即可。用 mul_S 表示将 S 划分为若干互不连边的强联通分量的方案数（加上了容斥系数）

则有：

dp_S = 2^{e_S} + \sum_{\varnothing \subset T \subseteq S} mul_T 2^{e_{S-T}} \times 2^{s(T,S-T)}

以及

mul_S = -dp_S - \sum_{\varnothing \subset T \subset S,\min(S) = \min(T)} dp_T mul_{T-S}

注意，第一遍计算 mul_S 时，dp_S 仍然未确定（显然也不需要统计入 dp_S）。在计算完成 dp_S 之后再加回去即可。

直接做是 O(n3^n) 的，懒得进一步优化了。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=15+5,MAXM=100000+10,MOD=1e9+7;
int n,m,e[MAXN][MAXN],pw[MAXN*MAXN],dp[MAXM],ori[MAXM],nb[MAXN],mul[MAXM];
int calc(int s1,int s2) {
    int cnt=0;
    ffor(i,1,n) if(s1&(1<<i-1)) cnt+=__builtin_popcountll(nb[i]&s2);
    return pw[cnt]; 
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ffor(i,1,m) {int u,v;cin>>u>>v,e[u][v]=1,nb[u]|=(1<<v-1);}
    pw[0]=dp[0]=ori[0]=1;
    ffor(i,1,m) pw[i]=pw[i-1]*2%MOD;
    ffor(i,1,(1<<n)-1) {
        int c=0;
        vector<int> pos;
        ffor(j,1,n) if(i&(1<<j-1)) pos.push_back(j);
        for(auto p1:pos) for(auto p2:pos) c+=e[p1][p2];
        for(int S=i;S;S=(S-1)&i) if((S&-S)==(i&-i)) mul[i]=(mul[i]-dp[S]*mul[i-S])%MOD;
        dp[i]=ori[i]=pw[c];
        for(int S=i;S;S=(S-1)&i) dp[i]=(dp[i]+mul[S]*ori[i-S]%MOD*calc(S,i-S))%MOD;
        mul[i]=(mul[i]-dp[i])%MOD;
    }
    cout<<(dp[(1<<n)-1]%MOD+MOD)%MOD;
    return 0;
}