洛谷3349 [ZJOI2016]小星星

Luogu

LOJ

UOJ

分析

神仙容斥?

考虑这样一个 DP:设 $f[i][j]$ 表示以 $i$ 为根的子树,$i$ 映射到了 $j$ 的方案数。这里允许多个点映射到同一个点。

这样子 DP 答案显然会偏大,原因在于图中有一些点没有被映射到。

考虑容斥有多少个点没有被映射,可以发现容斥系数是 $(-1)^i$ ,这里的 $i$ 表示 $i$ 个点没有被映射到。

于是只需要 $2^n$ 枚举所有情况,然后 $O(n^3)$ 树形 DP 出方案数,再容斥计算答案即可。时间复杂度 $O(2^nn^3)$ ,Luogu 上大概要吸氧才能过。

考虑一个优化:把 $f[i][j]$ 的定义改为以 $i$ 为根的子树,$i$ 映射到了可映射的点中的第 $j$ 个的方案数。这样子每次树形 DP 就是 $O(sz^3)$ 的了,总时间复杂度就变成了不满的 $O(2^nn^3)$ 。实测吸氧后可以跑进洛谷最优解第一版。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=17+10;

int n,m,lim;
int G[N][N],ok[N];
int sta[N],top=0;
ll f[N][N];

struct edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

inline void dfs(int u,int fa) {
    for (re int i=1;i<=top;++i) f[u][i]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        for (re int j=1;j<=top;++j) {
            ll s=0;
            for (re int k=1;k<=top;++k)
                s+=f[v][k]*G[sta[j]][sta[k]];
            f[u][j]*=s;
        }
    }
}

int main() {
    n=read(),m=read(),lim=1<<n;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        G[u][v]=G[v][u]=1;
    }
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    ll ans=0;
    for (re int i=0;i<lim;++i) {
        top=0;
        for (re int j=1;j<=n;++j)
            if (i&(1<<(j-1))) sta[++top]=j;
        dfs(1,0);
        ll res=0;
        for (re int j=1;j<=top;++j) res+=f[1][j];
        if ((n-top)&1) ans-=res;
        else ans+=res;
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 28 PM

发表评论