TopCoder SRM 725 Div1 Med: HiddenTree

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → 掲載されてないぽい (unrated だから？)

頂点が 個あり、それぞれの頂点について値 が与えられる。各頂点に という値を適切に決めたとき、以下の条件を満たす DAG がいくつできるか求めよ。なお、 の値が異なっていても、グラフが同型 (頂点のラベルと辺の対応が完全に一致する) であれば区別しないものとする。

• それぞれの頂点について、入次数は高々
• 頂点 から到達できる頂点集合 ( を含む) を とおくとき、 を満たす

解説

Div2 Hard と方針はほぼ同じで、数え上げパートが増えただけです。

方針は Div2 Hard の方の記事 を参照してください。

ソースコード

int dp[1 << 14];
class HiddenTree {
    public:
    int count(vector<int> b) {
        int N = b.size();
        sort(b.begin(), b.end());

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        int ret = 0;
        for(int i=0; i<N; i++) {
            for(int bit=0; bit<(1<<i); bit++) {
                if(i != 0 && !(bit >> (i-1) & 1)) continue;
                for(int mask=bit;; mask=(mask-1)&bit) {
                    ll sum = 0;
                    for(int k=0; k<i; k++) {
                        if(mask >> k & 1) sum += b[k];
                    }

                    if(sum < (ll)b[i]) {
                        int nbit = (bit ^ mask) | (1 << i);
                        (dp[nbit] += dp[bit]) %= MOD;
                        if(i == N-1) (ret += dp[bit]) %= MOD;
                    }

                    if(mask == 0) break;
                }
            }
        }
        return ret;
    }
};