Topcoder 15279 SpanningSubgraphs

题目链接

Topcoder 15279 SpanningSubgraphs

题目大意

有一张 \(n\) 个点，\(m\) 条边的图，对于每个 \(k\in[n-1,m]\)，求出大小为 \(k\) 的能使图连通的边集数量。

\(1\leq n\leq 15\)，\(1\leq m\leq 200\)

思路

考虑朴素的容斥，设 \(siz_S\) 为两个端点都在点集 \(S\) 中的边数，\(dp_{S,k}\) 为在点集 \(S\) 中满足条件的 \(k\) 元边集的数量。经过简单思考可以得到转移式：

\[dp_{S,k}=\binom{siz_S}{k}-\sum_{T\subset S,lowbit(S)\in T}\sum_{i=0}^k dp_{T,i}\cdot \binom{siz_{S-T}}{k-i} \]

为了去重，这里钦定 \(T\) 中包含 \(S\) 的最小元素。由于每次要枚举子集和边数，这么做是 \(O(3^nm^2)\) 的，\(5.7e9\) 运算量显然太大了，需要优化。

接下来的思路参考了 Petr Mitrichev 的 博客，这个转移式已经没有什么优化的余地了，而且 \(dp\) 的两维状态也不可省略，于是我们只能优化计算。这里的突破口在于组合数上，通常计算时我们会将组合数预处理好直接带入，但是现在我们要 拆开组合数，在计算组合数的同时把转移式的值一起算好。转移式的 \(S\) 不可忽略，我们枚举 \(S\)，对于每个 \(S\) 进行一次如下的计算：

引入一个辅助数组 \(g_{i,j}\)，\(i\) 是 \(S\) 中边数，\(j\) 是 \(T\) 中的边数。初始令 \(g_{i,j}=\sum_{siz_{S-T}=j}dp_{T,i}\)，这些集合 \(T\) 对 \(S\) 的组合数贡献是相同的，在带上系数的情况下，用 \(g\) 算组合数：

\[g_{i,j-1} \leftarrow g_{i,j}\;,\;\; g_{i+1,j-1}\leftarrow g_{i,j} \]

注意到 \(siz_T\) 的范围各不相同，为了统一结果，第二维要从高往低算。于是 \(g_{i,0}\) 即为先前我们所需要的式子，原先的转移式简化成了 \(dp_{S,k}=\binom{siz_S}{k}-g_{i,0}\) 。

\(g_{i,j}\) 初始化 \(O(3^nm)\) ，计算 \(O(2^nm^2)\)，\(dp\) 转移直接降到了 \(O(2^n)\)，所以总复杂度 \(O(3^nm+2^nm^2)\)，计算量 \(3e8\)，我们可以通过只枚举包含 \(1\) 的连通块再加速一点，可以通过此题。

Code

#include
#include
#include
#define mem(a,b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 15
#define M 205
#define mod 1000000007
using namespace std;

int C[M][M], siz[1< count(int n, vector a, vector b){
        int m = a.size();
        int all = (1< ans;
        rep(i,n-1,m) ans.push_back(f[all][i]);
        return ans;
    }
} solve;

int main(){
    int n, m, u;
    vector a, b;
    cin>>n>>m;
    rep(i,1,m) cin>>u, a.push_back(u);
    rep(i,1,m) cin>>u, b.push_back(u);
    vector ans = solve.count(n, a, b);
    for(int k : ans) cout<