# UCUP 13 ## A si a_1,..,a_n と X が与えられる {1,..,X} の subset S のうち条件を満たす者は何通り? - 条件: Sで張られるvector space (by xor) の基底として{a_1,..,a_n}がとれる ## B yo ## F yo,si sugoi given N (N choose 2) 本の辺をランダムに並び替えて左からunionfindしたとき、pathグラフになる確率は? ## G yo K = 1 : diameter ## K yo --- ## --------------Solved------------------ ## E yo ## D su ## C si ## J su 配列 a に対して f(a) := a の連続部分列のうち回文の個数 と定義する。 例えば、f([1, 2, 1]) = 4 入力として n, m, k が与えられる。 長さ n の数列であって各要素が 1, ..., m であるようなものは m^n 通りあるが、これらのうち f が最小値を取るようなものだけを考えたとき、辞書順で k 番目に小さいものを出力せよ。 ↑↑↑ ここまで問題文 考察: - m >= 3 なら f の最小値は n になる。[1, 2, 3, 1, 2, 3. ...] のように並べればいいので - だから同じ値が距離 1 or 2 に存在しないような数列のみ考えればいい - m = 2 なら - n >= 6 からは以下の 12 通りの列を繰り返しただけのやつになる ``` 001011... 001101... 010011... 010110... 011001... 011010... 100101... 100110... 101001... 101100... 110010... 110100... ``` ## H si subsequence が ちょうど N 個あるbinary文字列のうち辞書順でK番目に小さいものを出力 N,K <= 10^9, 100テストケース 実験かなあ ## L yo ## I yo -> su