bzoj4455 [Zjoi2016]小星星

た入场券 2021-11-01 09:38 233阅读 0赞

题目描述：

[bz][]

[luogu][]

题解：

大力容斥+卡常。

考虑$dp\[i\]\[j\]$表示点$i$子树选完且点$i$对应点$j$的方案数，很好转移。

然后大力容斥，此时容斥系数$-1^i$。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    typedef unsigned long long ll;
    const int N = 20;
    template<typename T>
    inline void read(T&x)
    {
        T f = 1,c = 0;char ch=getchar();
        while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
        x = f*c;
    }
    int n,m,mp[N][N],hed[N],cnt;
    ll ans;
    struct EG
    {
        int to,nxt;
    }e[2*N];
    inline void ae(int f,int t)
    {
        e[++cnt].to = t;
        e[cnt].nxt = hed[f];
        hed[f] = cnt;
    }
    int use[N],sta[N],tl;
    ll dp[N][N];
    void dfs(const int u,const int f)
    {
        for(register int i=1;i<=tl;++i)dp[u][i]=1;
        for(register int j=hed[u];j;j=e[j].nxt)
        {
            int to = e[j].to;
            if(to==f)continue;
            dfs(to,u);
            for(register int k=1;k<=tl;++k)
            {
                ll tmp = 0;
                for(register int i=1;i<=tl;++i)if(mp[sta[i]][sta[k]])
                    tmp+=dp[to][i];
                dp[u][k]*=tmp;
            }
        }
    }
    int main()
    {
        read(n),read(m);int u,v;
        for(register int i=1;i<=m;++i)
            read(u),read(v),mp[u][v]=mp[v][u]=1;
        for(register int i=1;i<n;++i)
            read(u),read(v),ae(u,v),ae(v,u);
        for(register int i=1;i<(1<<n);++i)
        {
            int tmp = n;tl = 0;
            for(register int j=1,now=i;j<=n;++j,now>>=1)
                if(now&1)tmp--,use[j]=1,sta[++tl]=j;
                else use[j]=0;
            dfs(1,0);ll now = 0;
            for(register int j=1;j<=tl;++j)
                now+=dp[1][j];
            if(tmp&1)ans-=now;
            else ans+=now;
        }
        printf("%llu\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/LiGuanlin1124/p/11061021.html

[bz]: https://www.lydsy.com/JudgeOnline/problem.php?id=4455
[luogu]: https://www.luogu.org/problemnew/show/P3349
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/05fd10d93b8e45409a2063122bba668d.png