競技プログラミング用 知識集積所
ARC206C - Tree Sequence
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
考え方
問題の必要十分条件を考える。
まず、必要条件。
n=1のときは明らかに成り立つ。
n=2の場合、これが木になるのは、a[i]==i+1またはa[i+1]==iであるとき。
これが任意のiで成り立つことが必要である。
逆に十分条件。
さきほどの条件が満たされていれば、頂点lから頂点rまで番号順に一本道の木ができる。
したがって、この問題は、「全ての場所でa[i]==i+1またはa[i+1]==iが成り立つようなaの作り方は何通りか？」と読み替えることができる。
これは途中に値の指定があるところで区切って考え、それぞれの区間の決め方の積を取ればよい。
まず、必要条件。
n=1のときは明らかに成り立つ。
n=2の場合、これが木になるのは、a[i]==i+1またはa[i+1]==iであるとき。
これが任意のiで成り立つことが必要である。
逆に十分条件。
さきほどの条件が満たされていれば、頂点lから頂点rまで番号順に一本道の木ができる。
したがって、この問題は、「全ての場所でa[i]==i+1またはa[i+1]==iが成り立つようなaの作り方は何通りか？」と読み替えることができる。
これは途中に値の指定があるところで区切って考え、それぞれの区間の決め方の積を取ればよい。
各区間の決め方は「区間の左端がa[i]==i+1になっているか」「区間の右端がa[i+1]==iになっているか」によって4パターンに分かれる。
まず、どちらも満たさない場合、明らかに0通り。
前者だけ満たす場合、全ての場所でa[i]==i+1にするしかないので、1通り。
後者だけ満たす場合、全ての場所でa[i+1]==iにするしかないので、1通り。
まず、どちらも満たさない場合、明らかに0通り。
前者だけ満たす場合、全ての場所でa[i]==i+1にするしかないので、1通り。
後者だけ満たす場合、全ての場所でa[i+1]==iにするしかないので、1通り。
どちらも満たす場合は、途中までa[i]==i+1にして、任意の値を1つ挟んで、そこから先はa[i+1]==iにするので、パターン数は基本的に区間の長さ×選べる数の数。
ただし、{1,2,3,2,3,4}が3番目と4番目のどちらが任意に選んだのかわからないものが隣接2項の選び方分、つまり項数-1だけあり、これを引く必要がある。
ただし、{1,2,3,2,3,4}が3番目と4番目のどちらが任意に選んだのかわからないものが隣接2項の選び方分、つまり項数-1だけあり、これを引く必要がある。
解答例
注意点
long long型を使う
解答がint型には収まらないことがある。
