有大佬曰过,像这种全排列计数类的问题,常常是子集DP。
也就是可以考虑,对于树上每一个节点x,它所在的子树,在图上的映射集合是s,并且x对应着图上的点i的状态f(x,i,s),进行DP。
这样复杂度还是太高。
发现复杂度瓶颈是在枚举子树的映射集合那里,而之所以要这么做,是因为树上点和图上点之间是一一映射。而假设映射不要一一对应,算出方案后,通过缩小映射集合进行容斥的方法是一个套路(虽然我这个蒟蒻是才知道这东西是套路),所以考虑容斥。
记f(x,i)表示树上点x对应图上点i,其子树的映射方案数。这东西的dp是$O(n^3)$的。
可能不是一一映射,也就是会有图上点对应不到树上点,那么就枚举并删掉那个没有被对应到的图上点,继续dp后从答案中减去。当然这样也会多算有两个图上点对应不到的情况,又要加上。然后还要减去有四个点对应不上的情况……
总之,复杂度是$O(n^3 2^n)$的,不过,每次DP考虑的图上点往往达不到$O(n)$级别……所以,这个复杂度也达不到这么大,具体是多少我太菜了算不出……就这样。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
int n,m,tot,js;LL ans;
int h[20],ne[40],to[40],l[20][20],bin[20],p[20];LL f[20][20];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dp(int x,int las) {
    for(RI i=1;i<=js;++i) f[x][p[i]]=1;
    for(RI i=h[x];i;i=ne[i]) {
        if(to[i]==las) continue;
        dp(to[i],x);
        for(RI j=1;j<=js;++j) {
            LL res=0;
            for(RI k=1;k<=js;++k)
                if(l[p[j]][p[k]]) res+=f[to[i]][p[k]];
            f[x][p[j]]*=res;
        }
    }
}
int main()
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(RI i=1;i<=m;++i) scanf("%d%d",&x,&y),l[x][y]=l[y][x]=1;
    for(RI i=1;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    bin[1]=1;for(RI i=2;i<=n+1;++i) bin[i]=bin[i-1]<<1;
    for(RI zt=1;zt<bin[n+1];++zt) {
        js=0;
        for(RI i=1;i<=n;++i)
            if(zt&bin[i]) p[++js]=i;
        dp(1,0);LL res=0;
        for(RI i=1;i<=js;++i) res+=f[1][p[i]];
        if((js&1)==(n&1)) ans+=res;
        else ans-=res;
    }
    printf("%lld\n",ans);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

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

你是机器人吗? =。= *