SRM585 Div1 Easy "TrafficCongestion"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11361
訳
いくつかの都市があり、道路でつながっている。道路網の構造は、都市をノード・道路をエッジとしたときに完全二分木になっている。
あなたは木の高さを表すint treeHeightが与えられる。(完全二分木の高さとは、木のルートノードとリーフノードを結ぶ道路の数である)したがって、2^(treeHeight+1)-1だけの都市と、2^(treeHeight+1)-2だけの道路の数があることになる。
私たちはいくつかの車をこの道路網に送りたい。それぞれの車は出発する都市から目的の都市まで、同じ年を2度通らずに走る。(それぞれの車のルートは、出発地と目的地によって、一意に決められる事に注意せよ)出発する都市と、目的の都市は同じでもよく、この場合車は1つの都市を訪れるだけである。
私たちの目的はそれぞれの都市を訪れる車をちょうど1台にして、車を送り出すことである。このようにしたときに、送り出す車の最小を返せ。
制約
0 <= treeHeight <= 10^6
Editorialsを見て
一応実装してみた。
イマイチ理解できない・・・はぁ・・・
Div2のとは制約のみ違います。
ソースコード
const int MOD = 1000000007; long long s[1000050]; class TrafficCongestion { public: int theMinCars(int treeHeight){ long long ans = 1; s[0] = 1; s[1] = 2; for( int i = 2; i <= treeHeight; i++ ){ ans = (s[i-2] * 2 + 1) % MOD; s[i] = (ans + s[i-1]) % MOD; } return (int)ans; } };