P3349 [ZJOI2016] 小星星 题解 - 容斥学习

· · 个人记录

前言

之前从来没学习过容斥模型，这次这个题作为我的第一个容斥例题学习。

正文

0x00 问题分析

这个问题可以抽象为：给定一个图 G 和一棵树 Tree 要求对于树重新编号，编号是一个 n 的排列，假如树上任意一个父亲编号为 x 任意其儿子的编号为 y 则需要满足在图 G 上有编号为 x 和 y 的连边。

显然有一个状压 dp ，即定义 dp_{i,x,S} 为树上原本标号为 i 的节点被标号为 x ，并且其子树使用了 S 这个集合中的编号。这样直接计算时间复杂度为 \mathcal{O}\left(n^33^n\right) 这样会直接 T 掉考虑优化。

可以发现时间复杂度卡在要考虑 S 这个限制。那么考虑去除 S 一维，直接跑多次 dp 每次限定一个可用于编号的集合 S 。但是这样就没有限制了，并没有办法保证排列了，但是可以保证边的限制合法。但是这样是典型的交容斥，如何理解呢？

考虑每一个解(不管是否是排列，只需要这个解边的限制合法)作为元素(这个元素是一个集合就是标号的一个子集，即 S )设所有解的集合为 U ，将这个解的 S 中的点作为其属性，我们要求的就是每一个含有这个属性(即编号)的集合 T ，设包含 i 这个编号属性的元素集合为 T_i 。要求的就是所有 T 的交。

0x01 容斥推导

根据容斥公式有：

\left|\bigcap_{i=1}^{n}T_i\right|=\left|U\right|-\left|\bigcup_{i=1}^{n}\overline{T_i}\right|

且对于任意集合 P_i 有：

\left|\bigcup_{i=1}^{n}P_i\right|=\sum_{m=1}^n\left(-1\right)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcup_{i=1}^{m}P_{a_i}\right|

即

\left|\bigcup_{i=1}^{n}\overline{T_i}\right|=\sum_{m=1}^n\left(-1\right)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m}\overline{T_{a_i}}\right|

实际上 \left|U\right| 就是可以用任意标号去标。

而对于

\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m}\overline{T_{a_i}}\right|

相当于在任意选了 m 个点不选的解的数量。发现这个统计是容易的即 \left|S\right|=n-m 时的解的数量。

记 Cnt_i 表示 \left|S\right|=i 时的解的数量，最终得到了：

Ans=Cnt_n-Cnt_{n-1}+Cnt_{n-2}\cdots

0x02 DP细化

现在可以放心的 DP 了，假设当前钦定可用于标号的点集为 S ，有：

Dp_{u,x}=\prod_{y\in S} \sum_{v\in son_u} Dp_{u,y}\times\left[G_{x,y}\right]

其中 \left[G_{x,y}\right] 表示在图 G 上是否有边 \left(x,y\right) 。

DFS DP 即可

0x03 代码实现

AC CODE

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE long long
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}

int n,m;
long long f[20][20];

std::vector<int> tree[20],scur;
std::bitset<20> graph[20];

void addEdge_tree(int u,int v){tree[u].push_back(v);tree[v].push_back(u);return;}
void addEdge_graph(int u,int v){graph[u][v]=graph[v][u]=1;return;}

void dfs(int u,int p){
    for(auto v:tree[u])
        if(v!=p)
            dfs(v,u);
    register long long sum;
    for(auto x:scur){
        f[u][x]=1;
        for(auto v:tree[u]){
            if(v==p) continue;
            sum=0;
            for(auto y:scur)
                sum+=f[v][y]*graph[x][y];
            f[u][x]*=sum;
        }
    }
    return;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,u,v,s,maxs;
    register long long ans=0;
    n=read();
    m=read();
    for(i=0;i<m;++i){
        u=read()-1;
        v=read()-1;
        addEdge_graph(u,v);
    }

    for(i=1;i<n;++i){
        u=read()-1;
        v=read()-1;
        addEdge_tree(u,v);
    }

    maxs=(1<<n);

    for(s=0;s<maxs;++s){
        scur.clear();
        for(i=0;i<n;++i)
            if((s>>i)&1) scur.push_back(i);
        dfs(0,0);
        if((n-scur.size())&1)
            for(auto id:scur)
                ans-=f[0][id];
        else
            for(auto id:scur)
                ans+=f[0][id];
    }

    print(ans);

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}

总结

容斥的题首先要想到一个次优的解法，并且想要优化的过程中需要发现其符合容斥的性质才能完成。