题解 P4871 【Oier们的镜子(mirror)】

· · 题解

【题意】定义有根树上一个结点的权值等于整个子树内的节点权值和，现给出n(n\le15)个节点的权值\{w_n\}，限制每棵树高度不超过2，求满足要求的带权森林个数。

【做法】考虑状压dp，设f[i,j]为按w排序小大排序后前i个节点所构成的森林中，高度为1的树集合为j的方案数，转移有

f[i,j]\to f[i+1,j+\{i+1\}]

即考虑让i+1作为高度为1或2的树的树根。注意到当|k|=1时，存在让i+1作为k中唯一点e_0的儿子的方案。显然仅当w_i单调不降时能取到所有决策。

【复杂度的推导】

\sum_{i=0}^{2^n-1}2^{\mathbb{popcount}_i} =\sum_{i=0}^n(n,i)2^i=\sum_{i=0}^n(n,i)1^{n-i}2^i=(1+2)^n=3^n

总时间复杂度为O(n3^n)，需要剪枝。 

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;

int n,w[15],sum[1<<15];
int lmt,f[16][1<<15];

inline int lbt(int x) {return x&-x;}
inline void add(int&x,int y) {if((x+=y)>=mod) x-=mod;}

int main() {
    scanf("%d",&n);
    for(int i=0; i<n; ++i) scanf("%d",w+i); sort(w,w+n);
    for(int i=0; i<n; ++i) sum[1<<i]=w[i]; lmt=1<<n;
    for(int i=0; i<lmt; ++i) {
        if(i!=lbt(i)) sum[i]=sum[i-lbt(i)]+sum[lbt(i)];
    }
    f[0][0]=1;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<lmt; ++j) if(f[i][j]) {
            add(f[i+1][j|(1<<i)],f[i][j]);
            for(int k=j; k; k=(k-1)&j) if(w[i]==sum[k]) {
                add(f[i+1][j^k],f[i][j]);
                if(k==lbt(k)) add(f[i+1][j^k],f[i][j]);
            }
        }
    }
    int ans=0;
    for(int i=0; i<lmt; ++i) {
        add(ans,f[n][i]);
    }
    printf("%d\n",ans);
    return 0;
}