---
# System prepended metadata

title: UCUP 13

---

# 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
