問題概要
正整数からなる列 $w$ が与えられる.4 要素からなる $w$ の部分列をとって $\{ a, b, c, d \}$ としたとき,$ac = bd$ となっているものの総数を求めよ.
- $4 \leq |w| \leq 1{,}000$
- $1 \leq w_i \leq 10^9$
正整数からなる列 $w$ が与えられる.4 要素からなる $w$ の部分列をとって $\{ a, b, c, d \}$ としたとき,$ac = bd$ となっているものの総数を求めよ.
';' + 1 つ以上の '_' + ';' という文字列を顔文字であるとする.例えば ";_;" や ";____;" は顔文字であるが,";;" や ";_" は顔文字ではない.
';' と '_' からなる文字列 $\mathit{ message }$ が与えられる.$\mathit{ message }$ を重複しない複数の部分列に分けたとき,部分列全てが顔文字となっていて,かつ全ての文字が丁度 1 つの部分列に属するような分け方は何通りあるか?
総数を $X$ として$X \bmod{ 10^9 + 7 }$ を求めよ.
$N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする.プレイヤーを A, B として,A は赤いトークンを,B は青いトークンを使う.
木の頂点は $0$ から $N - 1$ で番号付けられている.ゲームの初期状態は 3 つの配列 $\mathit{ tree }$, $A$, $B$ により与えられる.$\mathit{ tree }$ は木の形を表し,$i$ ( $1 \leq i \leq N - 1$ ) について,2 頂点 $i$, $\mathit{ tree }_{ i - 1 }$ 間に辺があることを表す.$A$ は赤いトークンの初期位置を,$B$ は青いトークンの初期位置を表す( $a \in A$ なる頂点 $a$ に赤いトークンがある.$B$ と青いトークンについても同様).
ゲームは Round と呼ばれる工程の繰り返しからなる.1 回のラウンドは,
という 2 つのフェーズからなる.
Round 終了後に,2 種類のトークンが存在する頂点が 1 つでもあれば,B の勝利となる.
B はできるだけ少ない Round 数で勝ちたいと思っていて,A はできるだけ多くの Round をプレイしたいと思っている.両者が最善を尽くすとき,プレイされる Round 数を求めよ.B が有限の Round 数で勝利できることは保証されている.
$N$ 頂点の木があって,各頂点は $0$ から $N - 1$ で番号付けられている.木の情報は配列 $\mathit{ parent }$ で与えられ,有効な $i$ について,頂点 $i + 1$ と $\mathit{ parent }_i$ の間に辺があることを表す.
この木の上で移動することを考える.あるノードからの一回の移動では,そのノードに隣接する頂点に移動することができる.
頂点 $0$ から始めて,$L$ 回以内の移動で到達できる頂点の数を求めよ(始点も含む)(重複は数えない).