TopCoder SRM585 Div1 Easy 250 TrafficCongestion

概要

高さ $ h $ の完全二分木がある.

この頂点たちを distinct な path で被覆したい. 被覆するために必要な path の数の最小値を求めよ.

制約

$ 0 \le h \le 10^6 $

解法

下から順番にへの字型にとっていくとよさげ.

最適性は, たぶん木DPをすることを考えると出るはず.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
// 231.16 pts

constexpr int mod = 1000000007;
int TrafficCongestion::theMinCars( int treeHeight ){
    long long res = 1;
    rep(i, treeHeight){
        res *= 2;
        if(i%2) ++res;
        else    res += mod-1;
        res %= mod;
    }
    return res;
}