BZOJ4455: [Zjoi2016]小星星【树形DP+容斥】

4455: [Zjoi2016]小星星

【题目描述】

传送门

【题解】

首先一个暴力的想法,F[i][j][S]表示i对应到j,集合为S的方案数。

每次枚举S的子集S',F[i][j][S]+=F[i][j][S']*F[son][k][S-S']

考虑先枚举S,不考虑子集,F[i][j][S]*=\sum F[son][k][S]

会发现有很多地方重复了,所以用容斥原理,减去不合法的方案数就可以了。

代码如下

#include<cstdio>
using namespace std;
typedef long long LL;
int n,m,Top,que[20];LL Ans,f[20][20];
bool vis[20][20];
struct Edge{
    int tot,lnk[20],nxt[405],son[405];
    void Add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
}E;
void DFS(int x,int fa){
    for(int i=1;i<=Top;i++) f[x][que[i]]=1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=fa){
        DFS(E.son[j],x);
        for(int i=1;i<=Top;i++){
            LL Now=0;
            for(int k=1;k<=Top;k++)
            if(vis[que[i]][que[k]]) Now+=f[E.son[j]][que[k]];
            f[x][que[i]]*=Now;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        vis[x][y]=vis[y][x]=1;
    }
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        E.Add(x,y),E.Add(y,x);
    }
    for(int i=1,END=(1<<n);i<END;i++){
        Top=0;
        for(int j=1;j<=n;j++)
        if(i&(1<<j-1)) que[++Top]=j;
        DFS(1,0);LL Now=0;
        for(int j=1;j<=Top;j++) Now+=f[1][que[j]];
        Ans+=Now*((Top&1)==(n&1)?1:-1);
    }
    printf("%lld\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部