必ず可能である。騙されるな。
頂点とそれを結ぶ辺があって、辺のもう片方の頂点番号が決まっていたとしても、頂点の番号を自由にいじることで辺は残せるので、グラフは連結が保たれる。
頂点 もう片方 ○---(3)---3 → 3以外の番号にする ○---(3)---4 → 3にする
なので、適当に1頂点を決めて、辺を伝って貪欲にまだ決まっていない頂点番号を決めていくことで、必ず連結にできる。
なんか $a,b,c,d$ が決まってると楽だなーと思いつつ、でも実は組み合わせは16通りしか無いことに気付く。
じゃあ場合分けできそう。
最初はbの操作しかできないのでそこから考える。 場合分けは、なんかこう決めたら都合よく場合が限定されそう、という部分から決めていくのがセオリー(多分)。 RPGのマップで宝箱を取り逃さないために、行き止まりっぽい方から調べるのと同じ。
たとえば b='A' なら 'AAB' になる。
もし、ここで a='A' ならa,bどちらを使っても'AAA…AB' にしかできない。cやdは使う機会さえ無く、1通り。
a='B'なら'ABAB'にでき、cが使えるようになる。
ここで、c='A'なら、'BB'という連続した'B'を作ることができない。 逆にその制約さえ守っていれば、最初に好きなだけ'AAA…AB'と並べておいて、'B'を好きな位置に挿入することで作れる。
最初は'A'、最後が'B'、'B'が連続しない、という制約での並べ方は簡単なDPを用いて求められる。
さて、最後にc='B'の時、'BB'を作れる。
この場合はほぼ任意の文字列を作れる。最初に必要なだけ'A'を並べておいて、'B'を好きな位置に挿入して好きなだけ拡張できる。
ただし、最後から2文字目は'A'から変えることができない。最初、最後も除いて $N-3$ 文字を自由に決められるので、$2^{N-3}$ となる。
b='B'の時も、前後と'A','B'を反転させれば同様に考えられる。
これで、場合分けが済んだ。
if b='A': if a='A': 1通り if a='B': if c='A': Bが連続しないパターン数 if c='B': 2^(N-3) if b='B': if d='B': 1通り if d='A': if c='B': Aが連続しないパターン数 if c='A': 2^(N-3)
A: 2 5 3 1 4 2 確率 1/5 で 2 を採用 2 x 1 は増加部分列にならなくなるためもう選べない 2 x 4 確率 1/3 で 4 を採用 2 x x 4 5 は増加部分列にならなくなるためもう選べない 2 x 3 x 4 確率 1/1 で 3 を採用 このような操作をした場合の最終的な長さは3となった 他の操作も含めると、この場合の答えは 266666671 (= 37/15) となる
こんな短いくせして意外と複雑な値になるじゃねえかおめえ……
最終的に出来上がる増加部分列が同じであっても、その選ぶ順番によって生成確率が異なる。
たとえば上記の例では、最初に2、次に $\dfrac{2}{3}$ で3か4を採用することで「2 3 4」が確定するが、もし最初に3を選ぶとそれだけで1,5が除外されて「2 3 4」が確定する。
どうにも完成形で分類しての計算は難しそう。
また、主客転倒でよくあるような「各 $A_i$ について、増加部分列に採用されて答えに寄与する確率」を求める方法もありそうだが、 確率を求めるには結局「それがいくつの候補の中から採用されたのか」というのが必要となる。
このためにまとめての計算、たとえば自身の左側/右側を独立に処理するなどができない。
直近の左/右で採用済みの数字を $A_l,A_r$ とすると、
あり得る $l,r$ のペアそれぞれについて試さないと無理そう(上手い方法があるのかも知れないが)。
以下のように更新できる。
l r i: ... 3 4 5 6 7 8 9 10 ... A: ... 5 2 7 11 9 1 8 10 ... j=5 3 --- 5 ------------ 10 DP[3][5] + DP[5][10] + 1 j=7 3 ---------- 7 ------ 10 DP[3][7] + DP[7][10] + 1 j=9 3 ---------------- 9 10 DP[3][9] + DP[9][10] + 1 DP[3][5] + DP[5][10] + DP[3][7] + DP[7][10] + DP[3][9] + DP[9][10] DP[3][10] = ------------------------------------------------------------------ + 1 3
これを、効率的に計算したい。
$DP[l][r]$ の計算に必要となる値は、$DP[l][○]$ か $DP[○][r]$ のようにいずれかが $l$ または $r$ であるのを利用する。
累積和として、以下を定義する。$N+2$ 本のFenwick Treeを作る。
なお、$x$ が $DP[l][r]$ の $l$ になる場合も $r$ になる場合もまとめて1つの累積和に押し込んでいるのは単にメモリ節約のためで、 「$x$ が $l$ に来る時用」「$r$ に来る時用」の2つに分けてもよい。
累積和をいい感じに用意しておいて、$DP[3][10]$ を求める際に次のようなものが用意できていれば嬉しい。
しかし、元の定義通りでは、$DP[3][6]$($A_6=11 \gt A_{10}=10$ なので対象外)や $DP[8][10]$($A_3=5 \gt A_8=1$ なので対象外)など、 $DP[3][10]$ を求める上では除きたい $DP$ の値も混じってしまう。
処理順序を工夫することで、「必要な値は埋まりつつ、不要な値は未処理でまだ埋まっていない状態」にする。
$A_i$ の小さい方から、それを $r$ とした $DP$ を埋めていくことにする。
$r$ を固定したら $l$ を全探索する。
この際、$l$ については $A_l$ が大きいものから順に埋めていくと上手くいく。
r rを固定 i: ... 3 4 5 6 7 8 9 10 ... この時点で、10より小さい値をrとしたDPは埋まっていて、 A: ... 5 2 7 11 9 1 8 10 ... 10より大きい値をrとしたDPは未処理 l r lを「l<r かつ Al<Ar」のものの中からAlが大きい順に固定 i: ... 3 4 5 6 7 8 9 10 ... [l, r) 間に採用可能な値はないので、DP[7][10]=0 A: ... 5 2 7 11 9 1 8 10 ... 済 l r lを次に固定 i: ... 3 4 5 6 7 8 9 10 ... [l, r) 間に採用可能な値はないので、DP[9][10]=0 A: ... 5 2 7 11 9 1 8 10 ... l 済 済 r lを次に固定 i: ... 3 4 5 6 7 8 9 10 ... [l, r) 間には2つ採用可能な値が存在 A: ... 5 2 7 11 9 1 8 10 ...
上例で、$DP[7][10]$ や $DP[9][10]$ は先ほど求めたし、$DP[5][7]$ や $DP[5][9]$ は $A_r=10$ まで進んできた時点で埋まっている。
逆に $DP[5][6]$ は、$A_6=11$ なので $DP[○][6]$ をまだ埋めていないので未処理、 $DP[8][10]$ は $A_8=1$ なので、$r=10$ に対する $l=8$ としたDPをまだ埋めていないので未処理となり、 きちんと必要な部分だけ埋まっていることがわかる。
よって、以下で更新できる。
$X$ や $Y$ が取り得る最大値は直径 $D$ になる。
まず直径をとる2頂点を見つける。
この2頂点が同色なら、他の頂点がどうあろうと $D$ になる。
まずこの場合は、$2^{N-1}D$ だけ答えに寄与する。
違う色の場合を考える。とりあえず左の頂点を白と固定して考えて、最終的な答えは2倍することにする。
○--?--?--?--?--?--?--● | | | ? ?--? ?--?
直径の性質として、どの頂点からも「その頂点から一番遠い点(の1つ)は直径の2点のいずれか」となる。
なので、直径の2頂点からの距離さえ考慮すればよい。それをまず全頂点について求めておく。
○--1--2--3--4--5--6--● | | | 2 4--5 6--7 ○--6--5--4--3--2--1--● | | | 7 5--6 3--4
この中で、距離の大きい方から、$\max(X,Y)$ をその値にできるかを考えていく。
7になり得るのは、「右下の頂点が白の時」か「左下の1頂点が黒の時」。
(A)このどちらかさえ満たしていればよく、またその時に(B)他の頂点はどうなっていてもよい。
(A)の場合の数は $2^{7になり得る頂点の個数}-1$、(B)は $2^{直径からの距離が両方7未満の頂点の個数}$。
よって、答えには $7 \times (2^2-1)2^9$ だけ寄与する。
6になり得る頂点は4つある。7の場合と同様に考えて、$6 \times (2^4-1)2^5$ だけ寄与する。
実はもう5が取り得る最小値であることが判明していて、4以下は考える必要は無い。
なぜなら、真ん中付近から伸びる枝先にある頂点は、白からの距離が5、黒からが6である。
○--○--2--3--4--5--●--● | | | ○ 4--○ ●--● ↑これ
最大値が $x$ (以下)となるには、上図のように $x$ より大きい距離となりうる頂点については全て小さい方(大きくない方)の色を選んでいるということだが、 それでも距離が5となる頂点があるため、4以下にはなり得ない。
よってこの場合は、この時点で残っている頂点は全てどちらになろうとも、$\max(X,Y)$ は5となる。
答えには $5 \times 2^5$ だけ寄与する。
このように、大きい方から処理しながら「小さい方を取ったときの最大値」を更新しておいて、それが現在処理中の値以下になったら、そこで打ち切るようにする。
ただし、一直線のグラフに関しては残る頂点がなくなるまでその条件に当てはまらないため、最後に打ち切ったかのように計算する。