SRM725 Lv2 : HiddenTree
作成日：2017.12.11
最終更新日：2017.12.11
問題概要
有向森は、有向グラフのうちどの頂点の入次数も高々1であるようなものである。
各頂点には正の重み$a_i$が割り当てられていて、$b_i$はその頂点から辺を辿って行くことができる頂点(自身も含む)の重みの和である。
$b$が与えられた通りになるような有向森の数を$10^9 + 7$で割った余りを求めよ。
但し、頂点の重みが異なるものも辺の張り方が同じであれば1つとして数える。
制約
$1 \leq |b| \leq 14$
$1 \leq b_i \leq 10^9$
考え方
入次数が高々1であることから、今まで見た頂点のうちまだ親がいないものの集合を保持していけば良さそうである。
また重みは正であり$b_i$は子よりも親の方が大きくなければならない。
このことから、$b_i$が小さい頂点から見ていけば良いことが分かる。
以上のことからbitDPを行えば良さそうなので、その遷移を考える。
$x$番目の頂点を見ている時は$(x-1)$番目の頂点に親はいないから、$2^{x-1}$$\leq mask$$< 2^x$からの遷移のみである。
まだ親のいない頂点$v$を子にすると$b_x$は$b_v$だけ増加することに注意すると、$x$の子にする頂点の$b_v$の和は$b_x$未満でなければならない。
よって、$mask$の部分集合でこの条件を満たすもの$subset$に対して$mask$から$(2^x+mask-subset)$に遷移する。
また、答えは$2^{|b|-1}$$\leq mask$$< 2^{|b|}$の範囲におけるmaskに対応する値の総和である。
このDPを行う時の計算量は$O(3^{|b|})$であるから十分高速である。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
class HiddenTree {
LL dp[1<<14];
LL s[1<<14];
public:
int count(vector<int> b) {
sort(b.begin(),b.end());
dp[0] = 0;
dp[1] = 1;
s[0] = 0;
int z = 0;
repp(mask,1,1<<(b.size()-1)){
while(mask>=(1<<(z+1))) ++z;
s[mask] = s[mask^(1<<z)] + b[z];
for(int subset = mask ; subset >= 0 ; --subset){
subset &= mask;
if(s[subset] >= b[z+1]) continue;
(dp[mask^subset^(1<<(z+1))] += dp[mask]) %= mod;
}
}
LL ans = 0;
repp(i,1<<(b.size()-1),1<<b.size()) (ans += dp[i]) %= mod;
return ans;
}
};解法まとめ
bitDPを行う。
最上位ビットが下から数えて$z$桁目である$mask$の遷移先は$2^{z+1}+mask-subset$である。
但し、$subset$は$mask$の部分集合のうちそれに含まれる頂点の$b_v$の総和$s_{subset}$が$b_{z+1}$未満であるものである。(13-21行)
答えは$2^{|b|-1}$$\leq mask$$< 2^{|b|}$の範囲におけるmaskに対応する値の総和である。(22-24行)
SRM725の他の問題 Lv1 Lv3