1~nを並び替えた数列があって、a番目とb番目を入れ替えるクエリがm個来るが、それぞれのクエリは1/2の確率でしか実行されない この時クエリをm個処理した後の反転数の期待値を求めよ p[i][j] : i番目 最後に足し合わせることで期待値が求まる。 Div1Dにして…

マンハッタン距離がdist以下のやつをunionfindでくっつけてから偶奇を見るだけ。 偶数のやつは何個使っても良くて、奇数のやつは偶数個使わなければいけないけど、 偶数のやつをP個, 奇数のやつをQ個とすれば Q >= 1の時 2 ^ (P + Q - 1) - 1, Q = 0の時 2 ^…

ポインタ難しいけどこの際listぐらいは実装できるようになろうと思ったら簡単だった(小並)こんな感じでいいのかな？ #include <cstdio> #include <cstdlib> using namespace std; struct Node{ Node *prev, *next; int val; }; Node *head, *tail; void init(){ head = tail =</cstdlib></cstdio>…