商品网站建设实验记录,公司名字大全 必过,做公司网站要营业执照吗,站长工具seo综合查询关键词题目描述 求一张有向图的强连通生成子图的数目对 $10^97$ 取模的结果。 题解 状压dp容斥原理 设 $f[i]$ 表示点集 $i$ 强连通生成子图的数目#xff0c;容易想到使用总方案数 $2^{sum[i]}$ 减去不为强连通图的方案数得到强连通图的方案数#xff0c;其中 $sum[i]$ 表示点集 $…题目描述 求一张有向图的强连通生成子图的数目对 $10^97$ 取模的结果。 题解 状压dp容斥原理 设 $f[i]$ 表示点集 $i$ 强连通生成子图的数目容易想到使用总方案数 $2^{sum[i]}$ 减去不为强连通图的方案数得到强连通图的方案数其中 $sum[i]$ 表示点集 $i$ 中边的数目。 考虑什么样的图不是强连通图缩点后入度为0的强连通分量对应的点集不是全集。 枚举这些入度为0的强连通分量对应的点集由于无法保证只有这些点构成的入度为0的强连通分量因此需要进一步容斥。推之可以发现容斥系数与这些点形成的强连通分量数目的奇偶性有关。 更具体来讲形成奇数个强连通分量时容斥系数为正即减去形成偶数个强连通分量为负即加上。 设 $g[i]i个点形成奇数个强连通分量的方案数-i个点形成偶数个强连通分量的方案数$ 那么枚举 $i$ 中编号最小的点所在连通块 $i-j$ 即枚举剩下部分 $x$ 不与编号最小的点相连的强连通分量 $j$ 则有 $g[i]-\sum\limits_{j\subset x}f[i-j]·g[j]$ 。注意此时的 $g$ 不包含 $i$ 只形成一个强连通分量的情况以便下面 $f$ 的容斥。 那么枚举钦定的入度为0的强连通分量 $j$ 就有 $f$ 的转移$f[i]2^{sum[i]}-\sum\limits_{j\subset i}2^{sum[i]-w[j]}·g[j]$ 其中 $w[j]$ 表示 $i$ 向 $j$ 连边的数目表示钦定的点不能被连边其它的随意连。 最后将只有一个强连通分量的方案 $f[i]$ 算进 $g[i]$ 。 答案就是 $f[2^n-1]$ 。 时间复杂度 $O(3^n)$ #include cstdio
#define N 32775
#define mod 1000000007
typedef long long ll;
int in[N] , out[N] , cnt[N] , sum[N] , w[N];
ll b[215] , f[N] , g[N];
void dfs(int i , int j)
{if(i (j - 1)) dfs(i , i (j - 1));w[j] w[j - (j -j)] cnt[in[j -j] i];
}
int main()
{int n , m , i , j , x , y;scanf(%d%d , n , m);b[0] 1;for(i 1 ; i m ; i ){scanf(%d%d , x , y) , x -- , y -- ;in[1 y] | 1 x , out[1 x] | 1 y;b[i] b[i - 1] * 2 % mod;}for(i 1 ; i (1 n) ; i ){x i - (i -i) , cnt[i] cnt[x] 1 , sum[i] sum[x] cnt[in[i -i] i] cnt[out[i -i] i] , f[i] b[sum[i]];dfs(i , i);for(j x ; j ; j x (j - 1)) g[i] (g[i] - f[i ^ j] * g[j] % mod mod) % mod;for(j i ; j ; j i (j - 1)) f[i] (f[i] - b[sum[i] - w[j]] * g[j] % mod mod) % mod;g[i] (g[i] f[i]) % mod;}printf(%lld\n , f[(1 n) - 1]);return 0;
}转载于:https://www.cnblogs.com/GXZlegend/p/8678089.html
