2020-03-06

重心分解

参考文献
https://www.hamayanhamayan.com/entry/2017/12/19/152143
https://qiita.com/drken/items/4b4c3f1824339b090202

木の重心: その頂点を取り除いたときにできる部分木の要素数が元の半分以下になる頂点
重心は1個か2個必ず存在する

部分木の要素数を求める木DPを行うことで重心列挙ができる
実装例

vector<vector<ll>> g(n);  
  
vector<ll> sz(n, 1), centroid;  
void dfs(ll v, ll p) {  
    bool iscentroid = true;  
    for(auto to: g[v]) if(to != p) {  
        dfs(to, v);  
        if(sz[to] > n/2) iscentroid = false;  
        sz[v] += sz[to];  
    }  
    if(n-sz[v] > n/2) iscentroid = false;  
    if(iscentroid) centroid.push_back(v);  
}

重心を意識すると構築を考えやすいとか
列の中心の代わりに重心を使うと列だけじゃなくて木でも解けるとか例題1 例題2
を見たことがある

https://www.quora.com/q/threadsiiithyderabad/Centroid-Decomposition-of-a-Tree
重心分解を行うと木に分解できる．この木の特徴として
* 元の木と同じ $N$ 頂点の木である(辺集合が違う)
* 木の高さは $O(\log N)$
サイズを二分割することを繰り返しているので
* 重心分解した後の木で頂点 $A,B$ のLCAは，元の木におけるパス $A,B$ に含まれる
* 重心分解した後の木は $O(N \log N)$ 個のパスに分解でき，任意のパスは異なる2つのパスのmergeで表せる
各頂点について根の方向へ向かう $O(\log N)$ 個のパスを保持しておく．LCAまでのパスを取ってくると2つのパスのmergeで表せる．

重心分解の実装

重心を見つける
その重心をグラフから取り除く
取り除いた後にできる連結成分それぞれについて，再帰的に同じことをする

Problem - 321C - Codeforces

重心分解のときの再帰の深さに対応するアルファベットを配置する
$2^26$ は頂点数より大きいので全パターンで構成可能

https://codeforces.com/contest/321/submission/72283144

パスの数え上げ

以下は条件を満たすパス（など）の数を数え上げる系の問題
分割統治で条件を満たす区間（など）の数を数え上げることを重心を用いることで木上でも行える

分割統治: [l,mid) [mid, r) に分割しそれぞれ解いてマージを繰り返す

// [l, r) について解く  
void dfs(ll l, ll r) {  
    ll mid = (l+r)/2;  
    // mid をまたぐような分について計算  
    // [l,mid) と [mid,r) と midをまたぐような分 の結果をマージする  
}

毎回区間が半分になっていくので，midをまたぐ分の計算に $O(r-l)$ かけたとしても $O(n\log n)$ で終わる
例題

No.1002 Twotone - yukicoder

パスグラフのときを考えると分割統治のように計算ができる
区間[l,r) で mid をまたぐようなちょうど2色含むようなパスを数える
区間[l,mid) の頂点xから頂点midまでのパスに含まれる色に対して，頂点midから頂点yまでのパスが含む色の条件を考える

頂点xから頂点midまでのパスが含む色が(色1,色2)
(色1,色2) or 色1のみ or 色2のみ or 何も含まない(ようするにy=mid)
頂点xから頂点midまでのパスが含む色が色1のみ
色1以外の色のみを含む or (色1,色i) (ただし色i!=色1)

あとは(色1,色2)を含むパスの数をそれぞれ数えておくことでmidをまたぐ分の計算ができ，分割統治で解ける

一般の木については頂点midのかわりに重心cを用いて，cをまたぐようなパスを数えることで同様に解ける

各パスについて両端点で数えてるので最後に2で割る必要がある
頂点xから頂点midまでのパスが含む色が色1のみかつ (色1,色i) のパターンについては，頂点xから頂点midまでのパスが含む色が(色1,色2) かつ色1のみ含む(色2のみ含む) のパターンを2倍して数えるようにすると楽

https://yukicoder.me/submissions/437248

CS Academy

転倒数についての記述があるが，実はこれはあまり関係ない． $K+1$ 要素の数列 $A$ とこれを反転した数列 $\text{rev}(A)$ の転倒数の和は $k(k+1)/2$ で一定である．

よって，あとは長さが $K$ のパスの個数を数えられればよい．twotone と同じ要領で重心分解して，該当する頂点の分だけ参照するように，重心を含むパスの個数を数える操作を繰り返す．

$\text{cnt} \lbrack i \rbrack = ($ 重心からの距離が $i$ の頂点の個数 $)$ とした配列を用意しておく．距離が $d$ の頂点が存在した場合，距離が $k-d$ の頂点とのパスが長さ $k$ になる．つまり $\text{cnt} \lbrack k-d \rbrack$ 個パスが存在する．ただし，重心から同じ方向にある，重心をまたがないような2点を選択してはならない．そこでその分を引く処理を行う．

これでパスの個数を数えたあと $k(k+1)/2$ を掛ければよい．

https://ideone.com/YZcEiI

Contest Page | CodeChef

twotoneと同じ要領で該当するパスを数え上げます

重心 $c$ を含むパスのうち長さが素数のものを数える． $\text{cnt_dist} \lbrack i \rbrack = ($ 重心からの長さが $i$ のパスの個数 $)$ とした配列を用意する．重心 $c$ からの距離が $d$ の頂点が存在するとき，長さが素数 $p_i$ となるパスの個数は "大体" $\text{cnt_dist} \lbrack p_i-d \rbrack$ 個である．

ただし，重心 $c$ に隣接する頂点のうち同一の頂点を根とする部分木内から2頂点を選択すると，重心 $c$ を含むパスとはならないことから，この分を数えてはならない．これを実現するための単純な方法として， $c$ に隣接する各方向の分の cnt_dist を数えておき，余計に数えた分を引くという方法があるが， $n$ 要素の配列である cnt_dist を各方向の分用意するとMLEしてしまう．

このMLEを回避するために cnt_dist をin-placeに取り扱う．まず，cnt_dist を一旦全部数え上げる．重心 $c$ に隣接する頂点 $to$ の方向に進んだ頂点を端点とする分を数える．まず， $to$ の方向に進んだ頂点の分，cnt_dist を減少させる．これで $c$ をまたがないパスの分を計算することはなくなったので， $\text{cnt_dist} \lbrack p_i-d \rbrack$ の総和を求めればよい．この後，減少させた cnt_dist の分を増加させて元に戻す．別の $to$ についても同様の処理を繰り返す．

このあと別の重心について計算を行うためには，cnt_dist を全て0にする必要がある． $n$ 要素の配列全てに0を代入しているとTLEだが，cnt_dist が非0であるような個数は重心分解している途中で重心から連結な頂点数で抑えられる．また， $\text{cnt_dist} \lbrack i \rbrack =0$ ならば $i$ 以上の位置についても全て0なので，0が出てきた時点で打ち切ってよい．

https://www.codechef.com/viewsolution/30036393

Problem - C - Codeforces

重心 $c$ を含むパスで $m$ の倍数となるものを数える
$x$ と $d$ 桁の数 $y$ をこの順につないだときに， $m$ の倍数となる条件を考える
$10^{d}x + y \equiv 0 (\text{mod } m)$
$x \equiv -10^{d}y (\text{mod } m)$

$x$ の方 $($ つまり，頂点 $u$ から重心 $c$ に向かうパスに対応する数 $)$ について $\text{mp} \lbrack x \rbrack = (x$ の個数 $)$ となるような map を持っておくと，各 $y$ について $mp \lbrack -10^{d}y \bmod m \rbrack$ を足し上げることで求められる．

重心 $c$ から同じ方向の2頂点を選ぶのはだめなので，その分を引く処理を Prime Distance On Tree と同様にin-placeに書くと，重心分解の分とmapの分でlog2個になる．

https://codeforces.com/contest/715/submission/72510660

http://techtipshoge.blogspot.com/2016/09/centroid-decomposition.html　に載ってる解法
重心 $c$ から $to$ の方向に進んだときの $y$ の分を計算し， $x$ の分を mp に足すという処理を繰り返す．次に $to$ を見る順番を逆にして，同様の処理を繰り返す．このとき各 $x,y$ の組み合わせ方をそれぞれ一回ずつ試しているので漏れなく数えられている．0のときだけ2回数えてしまうのでその分は2で割って調整する．

これでもlog2個な気がするけど，全組み合わせを参照するのがこれでもできるの賢い

Problem - E - Codeforces

重心 $c$ を含む回文にできるパス $P$ が存在 → $P$ 上の頂点に+1したい

並べ替えて回文にできるか？の判定は奇数個存在する文字種が高々1個か？でできます．このような判定を行うためのハッシュとして， $i$ 番目の文字種が奇数個存在するなら $i$ 桁目を1とするハッシュが有用です．このハッシュで1が立っている桁が1個以下なら回文にすることが可能と判定できます．パス $P(=A\to B), Q(=B\to C)$ をつなげたパス $A\to C$ のハッシュは $P,Q$ のハッシュのXORで高速に求められるのがうれしいポイントです．

$\text{cnt} \lbrack i \rbrack = ($ ハッシュが $i$ である重心を一端とするパスの個数 $)$ とした配列を用意します．ハッシュが x の頂点が存在した場合， $\text{cnt} \lbrack x \oplus (\text{回文にできるハッシュ})$ の分のパスをつくれます．このパスの分の数を重心側の頂点に伝播させることでパス上の頂点に一律に加算する処理を実現できます．

同じ方向の2頂点を選ぶ分を減算する処理を，in-placeに行えばokです．

https://codeforces.com/contest/914/submission/72518429

C - 木の問題

重心 $c$ をまたぐような，頂点 $v$ から距離 $k$ のパスの数を数える
$\text{cnt} \lbrack i \rbrack = ($ 重心からの距離が $i$ の頂点 $)$ とした配列を持っておく

$\text{query} \lbrack v \rbrack = ($ 頂点 $v$ のクエリに関連する $(k,i)$ のペアの集合 $)$ の形で持っておく
各頂点 $v$ にたどり着くタイミングで $\text{query} \lbrack v \rbrack$ のクエリに寄与する分を数える

in-placeっぽくcntを減算する処理をすればok

https://atcoder.jp/contests/yahoo-procon2018-final-open/submissions/10557394

数えるものをin-placeアルゴリズムっぽく配列とかを持つのかなり汎用性がある気がしてきた

重心分解した木の高さを利用する問題

以下は重心分解した後の木の高さは $O(\log N)$ なことを使うやつ

Problem - 342E - Codeforces

重心分解を行った木をつくっておく．この木上で $\text{dist_to_red} \lbrack v \rbrack = v$ を根とする部分木でvに最も近い赤い頂点までの距離を保持する．この情報が存在していれば，頂点 $v$ にもっとも近い赤い頂点までの距離は $\min(\text{dist_to_red} \lbrack u \rbrack + \text{dist}(u, v))$ $($ ただし，頂点 $u$ は $v$ から根までのパスに含まれる $)$ となる．

頂点 $v$ を赤くした際に， $\text{dist_to_red} \lbrack u \rbrack$ が変化する頂点 $u$ は $v$ から根までのパスに含まれる頂点 $u$ となる．この頂点 $u$ について $\text{chmin}(\text{dist_to_red} \lbrack u \rbrack , \text{dist}(u,v))$ を行えばよい．

重心分解を行った木の高さは $O(\log n)$ となるため，各クエリ $O(\log n)$ で答えられる．
(下の実装はLCAを $O(\log n)$ でやったので各クエリ $O(\log^2 n)$ です)

2点間の距離を計算するのに重心分解した後の木ではなく，元の木を使わなければならないことに注意

https://codeforces.com/contest/342/submission/72284993

SPOJ.com - Problem QTREE5

上の問題とほとんど同じだが，色を白から黒に戻す操作が加わった．部分木に存在する(白い頂点,白い頂点までの距離)のペアをsetで保持することでこの処理に対応する．色を変更する場合はsetへの挿入/削除，距離を答える場合はsetの中の距離が最小のものを求めることで処理できる．

setの要素数は各クエリで $O(\log n)$ 個増えるので，全クエリ通して $O(q \log n)$ 個でメモリは問題ない．

https://ideone.com/QhYs5x

距離を求めたい2頂点は $(v, v\text{の祖先})$ という関係が存在する．dist[i][j] = (i回目の分解の根からjまでの距離) を持っておくとLCAを使わずに配列を見るだけで $O(1)$ で求められるようになる．

BST maintenance | HackerRank

二分探索木を実際に構成する．平衡してないのでsort列とかを突っ込むと普通に $O(n^2)$ かかって終了するので， $x$ を追加するときは， $x$ 未満の最大の頂点の右の子・ $x$ 以上の最小の頂点の左の子のどちらかに追加するとすればよい．

重心分解して木をつくる．この木上で $a_0, a_1, a_2, \ldots$ と順に頂点をactiveに変更していく． $i$ 番目の頂点を追加したときの答えは，( $i-1$ 番目の頂点までの答え) + ( $i$ 番目の頂点とactiveな頂点の距離の総和) となる．したがって，各 $i$ について ( $i$ 番目の頂点とactiveな頂点の距離の総和) を求められればよい．

これを行うために，以下の3つの情報を保持する．

$\text{dist} \lbrack i \rbrack = (i$ を根とする部分木で $i$ からactiveな頂点の距離の総和 $)$
$\text{contribution} \lbrack i \rbrack = (\text{dist} \lbrack \text{par} \lbrack i \rbrack \rbrack$ に $i$ を根とする部分木が寄与する分 $)$
$\text{cnt} \lbrack i \rbrack = (i$ を根とする部分木でactiveな頂点の個数 $)$

( $i$ 番目の頂点とactiveな頂点の距離の総和) を計算する上で， $\text{par} \lbrack v \rbrack$ を根とする部分木の頂点を2タイプに分割する．

頂点 $v$ を祖先にする頂点
ボトムアップで計算していくので，前に計算した結果からわかる
頂点 $v$ を祖先にしない頂点
頂点 $v$ からこれらの頂点のうちactiveなものまでの距離の総和でok

これらをまとめると，( $i$ 番目の頂点とactiveな頂点の距離の総和) は $\text{dist} \lbrack a \lbrack i \rbrack \rbrack + \sum_{\text{par} \lbrack v \rbrack \text{はa \lbrack i \rbrack の祖先}} \text{dist} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{contribution} \lbrack v \rbrack + (\text{cnt} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{cnt} \lbrack v \rbrack ) \times \text{distance}(a \lbrack i \rbrack , \text{par} \lbrack v \rbrack )$ となる．
$\text{dist} \lbrack a \lbrack i \rbrack \rbrack$ → 頂点 $a \lbrack i \rbrack$ と部分木に存在するactiveな頂点までの距離の総和

$\sum$ の中の項については $v$ を祖先にしない頂点の分を計算する．
$\text{dist} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{contribution} \lbrack v \rbrack$ → 祖先にしない頂点について， $\text{par} \lbrack v \rbrack$ からactiveな頂点までの距離の和を求める
$(\text{cnt} \lbrack \text{par} \lbrack v \rbrack \rbrack - \text{cnt} \lbrack v \rbrack ) \times \text{distance}(a \lbrack i \rbrack , \text{par} \lbrack v \rbrack )$ → 祖先にしない頂点については $a \lbrack i \rbrack$ から $\text{par} \lbrack v \rbrack$ までの距離の分を足す必要がある

あとは $a \lbrack i \rbrack$ をactiveにしたときに情報をupdateできればよい．
$\text{dist} \lbrack \text{par} \lbrack v \rbrack \rbrack += \text{distance}(v, a \lbrack i \rbrack )$
$\text{contribution} \lbrack v \rbrack += \text{distance}(v, a \lbrack i \rbrack )$
$\text{cnt} \lbrack v \rbrack += 1$

TLが結構厳しくて，

2点間の距離は $O(1)$ LCA を使う
endlは使わない
llをできるだけ使わない

をしないと通らなかった
（ただTLEしたケースを手元で実行したら0.4secで動いた　謎）

https://ideone.com/JiLYK8

Problem - D - Codeforces

JAG2017のday2で使ったセットにあったやつ
頂点 $v$ から距離 $d$ 以下の頂点を色 $c$ にするクエリと頂点 $v$ の色を聞くクエリが飛んでくる

ググったら出てきたACコードを解読して投げたら通ったのでその解法のことを書くけど，ちゃんとケースつくると怪しい気がする

頂点 $u$ から距離が $d$ 以下の頂点に色 $c$ を塗るようなクエリ $i$ が存在する状況を保持する．
$\text{info} \lbrack u \rbrack = (d, i, c)$ で $d$ について降順となるように管理する
また，距離が $d$ 以下を塗るときにすでに存在する距離が $d$ 以下のクエリの分は上書きされて消えるので，その分はちゃんと消すように管理する

クエリ1が飛んできた場合，頂点 $v$ から根までのパスに含まれる頂点 $u$ についてinfo[u]を更新する．
クエリ2が飛んできた場合，頂点 $v$ から根までのパスに含まれる頂点 $u$ について $u,v$ の距離以下のinfo[u]のうち最も後に塗られた色を出力する．

https://ideone.com/L7986t

これinfoの要素数を5e4にしたあと，その頂点に5e4回クエリを飛ばすケースがつくれて，手元で試すと 3.78sec だった (TL3sec)

当たり前だけど重心分解した後の木上でうまくクエリに答えられるとは限らなくて，答えられる条件は一体何？
ある頂点から条件を満たす頂点までの距離の和みたいなのは色々できそう

2020-02-29

黄色difficultyとき直し

AtCoder

黄色difficultyあたりの適正難易度帯を昔やって忘れてるのもったいないので2周目

D - Connectivity

UF2本もって(道路のufの根,鉄道のufの根)のペアをkeyにまとめる

D - Ears

0, 偶数, 奇数, 偶数, 0 の5個の領域のどこにいるか？をDPのkeyに持つ
耳DP，DFAの状態をkeyに持つやつの一種だと認識している

D - No Need

dp[i枚目][総和がj] のナップサックDP
i枚目を加えたときにK以上になるならばiは必要
左右からDPしてi枚目がDPの最後にくるようなのを全てについて試す

C - Best-of-(2n-1)

高橋くん/青木くんが勝つ場合，それぞれについて計算して足す
A％がn-1回，B％がi回，C%がj回起きた後にA％が起きる確率 * (n+i+j) の総和
wolfram alphaに突っ込むと閉じた形の式が出てくる

C - +/- Rectangle

a a a a a
a -3a-1 a -3a-1 a
a a a a a
a -3a-1 a -3a-1 a
a a a a a
みたいな雰囲気でh*wの右下に負を突っ込む

D - Modulo Operations

自分より大きい数でmodをとっても何も起きないので降順sortしておく
dp[i番目まで][黒板の数がj] = 期待値

F - Laminate

dp[i番目まで][jと同じ高さにした][k回変更] = 操作回数

F - Small Products

dp[i番目まで][最後がj] = 何通り
$N/i$ が変化するのは $O(\sqrt{N})$ 個しかないのでそれだけ考えると間に合う

$\lfloor N/i \rfloor$ は $O(\sqrt{N})$ 個しか存在しない
実装

vector<ll> v;  
for(ll i=1; i<=n;) {  
    ll tmp = n/i;  
    v.push_back(tmp);  
    i = n/tmp + 1;  
}  
sort(ALL(v));

B - Even Degrees

辺数が奇数だと不可能
DFS木で子の数が奇数なら親との辺もつかって偶数にする
偶数ならそのままつなぐ

F - Engines

偏角ソートすると選ぶべきエンジンはある区間になる
$O(N^3)$ で全探索できる

F - Many Slimes

自分未満の最も大きいやつをつくるを繰り返す
これで構成できたらYes

E - guruguru

2周分確保しとく
xを1増やすと押す回数が1減る or a_{i+1}を超えて押す回数が増えるの2択
切り替わるタイミングを持っておいて平面走査みたいな雰囲気

D - Median of Medians

中央値を決め打つ二分探索

C - Lexicographic constraints

種類数決め打ち二分探索
文字列を持って遷移していく
文字が長くなるなら後ろにaを付け足す
それ以外の場合は prefixの $a$ 個の辞書順+1 を求める

C - Interval Game

左右にいったりきたりさせるのが最善

E - Don't Be a Subsequence

辞書順最小を求めるテクとして後ろからDPして前から復元
next[i][j] = i文字目以降で最初に現れる文字jの位置
dp[i] = 部分文字列[i,n)でかかる制約に違反しない最短の文字列の長さ
dp[i] = min(dp[next[i][j]] + 1)
各iについてどこからどの文字で遷移してきたかを覚えておいて復元する

忘れてたこのタイプ苦手
https://atcoder.jp/contests/arc081/submissions/9849717

E - Or Plus Max

高速ゼータ変換の要領でやる

B - Splatter Painting

上書きされる → 最後に塗られる色しか影響しない
dp[頂点v][距離d以下] = クエリは来たか？というmemo用の配列を持つ
メモ化再帰で計算量を抑えられる

なんかdがでかくても重心分解で解けるみたいなのみたことある気がする解いてないけど

D - Grid game

高橋くんは毎回移動しないといけない
青木くんはうまいこと動かして障害物の上にできるだけ早く当たるようにする
i行目でどの列まで移動できるか？を覚えておくと行ごとに遷移が高速にできる

E - Grouping

dp[i人以下のグループ][j人を振り分けた] = 何通り？
dp[i-1][j+ki] += dp[i][j] * 振り分け方の係数 (c <= k <= d or k = 0)

E - + Graph

全域木を適当に取る
1頂点決めると残りは全部決まる
決めた頂点を+1すると距離が奇数の頂点は-1で偶数の頂点は+1
後退辺とか頂点の重みが正の条件を満たすように+/-を制御

E - Tak and Hotels

ダブリングで各クエリlogで答える

E - Integers on a Tree

とりあえず偶奇の条件がかかる
木DPみたいに部分木ごとに考える
子に置ける範囲から頂点に置ける値の範囲が決まる
この範囲を持ってDP

D - Yet Another Palindrome Partitioning

int型で2²⁶は256MB程度
{A, B, …, Z} をkeyに持つことは可能

https://atcoder.jp/contests/code-festival-2017-qualc/submissions/9864552

E - Independence

クリーク内の辺を最小化するような，素なクリークでの分割を求めろ
補グラフを取ると，クリークは最大独立集合になる
最大独立集合で分割するので二部グラフでないと不可能
連結成分ごとに二択を決めるのをDP

D - Snuke Numbers

実験すると下の桁に9が並んでいる
変動させる候補を絞ることで全探索できる

E - Children and Candies

$x_i$ を変動させることを忘れて $f(x_1,x_2,\ldots,x_n)$ を求める
dp[i人目][j個] = 積の総和が3乗
$x_i$ を変動させるとしても遷移に係数がかかるだけ

D - K-th K

$x_i$ 番目に $i$ を置くのは確定
$\lbrack 0,x_i-1 \rbrack$ に $i$ 個， $\lbrack x_i+1,n-1 \rbrack$ に $n-1-i$ 個
$\lbrack 0,x_i-1 \rbrack$ は左に， $\lbrack x_i+1,n-1 \rbrack$ は右に詰めておくべき
実際に置いてみてだめだったらNO

F - Fork in the Road

辺削除がなければ $O(N^2)$ のDPでok
削除する辺は各頂点について高々1本 3乗でできる

C - ABland Yard

A,Bだけにしかいけない頂点を削除をトポソの要領でやる

C - Swaps

$A_i$ が大きい方から決めていくシミュレーションで通した
最大の $A_i$ が $A_i \gt B_i$ となっているのを直す
これは $A_i \leq B_j$ であるような $j$ について $\text{swap}(A_i, A_j)$ をすれば $A_i$ については直る
$(A_i, B_j)$ はok， $(A_j, B_i)$ について $A_j \leq B_i$ となるようにするには $A_j$ が最小の $j$ を選ぶとうれしそう
この操作を繰り返すシミュレーションでswap回数が $N-2$ 回以下ならばYes

B - Holes

凸包の内側の穴 → Rがめっちゃでかいから無視できる
穴の垂直二等分線からなる角度の比がそのまま角度になる

F - Lotus Leaves

最小カットまんま

B - Row to Column

ある行を全部黒にしたあと白がある列を塗る
全部黒にする行を全探索

D - Digit Sum

わからんので「n進数桁和」でググるとn-1で割るとうれしそうなことがわかる
$a_mb^m + a_{m-1}b^{m-1} + \cdots + a_1b + a_0 = n$ から
$a_m + a_{m-1} + \cdots + a_1 + a_0 = s$ を引く
左辺が $b-1$ の倍数になる → $b$ は $n-s$ の約数+1
約数は $O(\sqrt{n})$ 個なのでできる

n=sは気をつけないといけない
n=10¹¹だとi*i<=nでllでもオーバーフローする
3WAしましたが…
https://atcoder.jp/contests/arc060/submissions/9925762

C - Remainder Game

$2^k \gt 2^{k-1} + 2^{k-2} + \cdots + 2^1$ から $k$ を使わないで済むなら絶対に使わない
$k$ 未満のみを用いた遷移で $a_i$ から $b_i$ に移れるか？
$x \bmod i = y$ ならば $x$ から $y$ に辺を貼ったグラフで連結か？を見ればよい
移れない頂点があったら確定で $k$ を使う
$\text{can} \lbrack i \rbrack \lbrack j \rbrack = i$ 番目を $j$ にすることが可能か？を持って遷移していく

30分くらい
$a_i$ を割るときの条件とか考えてたけど冷静に考えて全部持てばいいだけ…
https://atcoder.jp/contests/agc022/submissions/9926136

D - Three Colors

辺の長さから三角形をつくれるかの条件は $R+G \lt B$ かつ $R+B \lt G$ かつ $B+G \lt R$
こういうのは補集合を数えるようにして包除
$R+G \geq B$ もしくは $R+B \geq G$ もしくは $B+G \geq R$ になる
包除で1つ満たす，2つ満たす，3つ満たすをそれぞれ数える
対称性があるので $R+G \geq B$ を満たすのを数えて3倍すればいい
2,3つ満たすのは $R=0, B=G$ みたいなのしかない
$(R,G,B \neq 0$ となる塗り方 $) - (R+B \geq G) \times 3$ を求めればいい

https://atcoder.jp/contests/tenka1-2019/submissions/10043958

E - Connected?

周上にあるやつしか関係なくて，カッコ列みたいなノリで繋げられるかどうかを判定

F - Xor Shift

$a_i \oplus b_i$ が全て一致するような巡回シフトを見つければいい
$a_1 \oplus b_1 = a_2 \oplus b_2$ なので $a_1 \oplus a_2 = b_1 \oplus b_2$ と変形
XORで隣接差分を取ると，巡回シフトをしたときに数列が一致するか？という問題になる
数列を2周分並べると一致する部分列があるか？という問題になる
あとはZ-algorithmではい

D - Game on Tree

grundy[v] = XOR(grundy[c]+1) がgrundyになるのを覚えてた
grundy[v] = XOR(子c側のgrundy) はgrundy数の定義から明らか
子cの部分木 + 辺1本からなるようなグラフのgrundyを知りたい
これは grundy[c]+1 となることが示せる

これは覚えてたけど実際解くとしたら実験grundy エスパーなのかなあ

F - Minimum Bounding Box

左右・上下で独立に考える
max, minになりうるのはL,Rそれぞれで高々1つ
短くなったあと長くなるみたいな感じになる
関数の形が変わる点ごとに考えればいい

F - Pass

$\text{dp} \lbrack i$ 文字目まで $\rbrack \lbrack$ 赤を $j$ 個 $\rbrack =$ 何通り
$i$ 文字目に赤を置けるか？ → 残りの赤の $(S$ の $i$ 文字目までの赤の個数 $) - j$ があるか

https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/10054660

E - Antennas on Tree

木のある高さの頂点集合について考える
頂点を根とする部分木のどこかにアンテナがあれば，その頂点については区別可能
全て区別できるようにする条件で木DP
根の次数が1とか2だと困るのでそうならないようにしておく

https://atcoder.jp/contests/apc001/submissions/10055055

C - Differ by 1 Bit

立ってるビットの数の偶奇が変化していくのでAとBの立ってるビットの数の偶奇が一致すると明らかにNO
それ以外は全部作れそう
全体にXOR Aすればスタートが0でゴールがA XOR Bに帰着できる

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 みたいに再帰的に v + {i} + v をつくっていくと変化させる桁を書いた列をつくれる
0?????, 10????, 110??? を順番に作っていくと 000000 → 111000 みたいなのをつくれる
この構成で全パターンつくれてるのでok

https://atcoder.jp/contests/agc031/submissions/10057284

D - Friction

コストに関連するのは隣り合うやつだけなので $W=2$ を解きたくなる
これは $\text{dp} \lbrack i \rbrack \lbrack j \rbrack =$ 左が $i$ 段，右が $j$ 段残っているときのコストでよさそう
$\text{dp} \lbrack i \rbrack \lbrack j \rbrack = \min(\text{dp} \lbrack i-1 \rbrack \lbrack j \rbrack , \text{dp} \lbrack i \rbrack \lbrack j-1 \rbrack ) + (i,j$ 段残っているときに同じ文字が隣接している個数 $)$
隣接している個数を $O(1)$ で求められるようにしたい
左の $a$ 番目，右の $b$ 番目が一致するならば， $i-j = a-b$ で $a,b$ 番目がまだなくなってないような $i,j$ のときに $a,b$ が隣り合っている
これは二次元グリッドで斜めの隣接した部分に+1なのでimosの要領で高速に求められる

$\text{dp2} \lbrack i \rbrack \lbrack j \rbrack = i-1$ 列目まで全部沈めて $i$ 列目が $j$ 段残ってる
みたいなDPをやろうとしたけど冷静に考えると全部独立なので $\text{dp} \lbrack h \rbrack \lbrack h \rbrack$ を足し合わせるだけでいい

https://atcoder.jp/contests/code-festival-2016-qualc/submissions/10059798

E - Sorted and Sorted

先頭に来るボールは黒1か白1のどちらか
黒1だけあるときに次に来るボールは黒2か白1のどちらか
先頭から決めていくDPをする

$\text{dp} \lbrack i \rbrack \lbrack j \rbrack = ($ 黒を $i$ ，白を $j$ まで並べるときに必要なswap回数 $)$
chmin(dp[i][j], dp[i+1][j] + (黒i+1を先頭にもっていくのに必要なswap回数))
すでに並べた分はswapしなくていいのでその分を引く
前計算しておけばこれはO(1)で求まる

https://atcoder.jp/contests/arc097/submissions/10083590

F - Enclosed Points

点iが何回数えられるか？
自分より上・下・左・右にある点だけしか選ばないようなパターンはだめ
これを別々に数えると，右上・右下・左上・左下だけを選ぶパターンを重複して数えているので包除の要領で引く

30分かかった…
https://atcoder.jp/contests/abc136/submissions/10084049

C - Nuske vs Phantom Thnook

森の連結成分の個数 = 頂点数 - 辺数
累積和を取っておけば各クエリO(1)
x,yの縦横が一番むずかしい

https://atcoder.jp/contests/agc015/submissions/10097392

B - Removing Blocks

取りうる全ての場合の和を求めるときに確率でやるやつ

https://atcoder.jp/contests/agc028/submissions/10097682

D - Two Sequences

$v$ のk bit目が1 → $T=2^k$ としたとき $v$ が $\lbrack T, 2T), \lbrack 3T, 4T), \lbrack 5T, 6T), \ldots$ の範囲内になる
$k$ bit目を参照するとき $k+1$ bitより上の桁は関係ない → $\text{mod} 2^{k+1}$ してもok
$a_i+b_j$ は高々 $4T$ なので $\lbrack T,2T), \lbrack 3T,4T)$ の範囲内になるのが何通り？を求めれば良い

https://atcoder.jp/contests/arc092/submissions/10118840

E - Weights on Vertices and Edges

重みが小さい順に追加していく
辺 $e$ を追加したとき， $e$ が属する連結成分の頂点の重みの和が辺の重み以上
→ 辺 $e$ の重み以下の辺をたどって到達できる辺は残せる
残せる辺集合の和集合を求める

これ苦手
https://atcoder.jp/contests/nikkei2019-qual/submissions/10120341

F - Distinct Numbers

key-valを交換するやつ
f(長さK) = 何回操作可能？ではなく f(x) = x回操作可能なKのうち最長とする
$f(x) = \sum_{i} \min(x, \text{cnt}_i)$ でこれは二分探索で求まる
$f(x)$ 上を二分探索すれば答えがわかる

これ苦手
https://atcoder.jp/contests/abc143/submissions/10121287

B - RGB Balls

前から貪欲に3色セットをつくっていくのが最小になる
この3色セットの最小が $a_i$ ，最大が $c_i$ となる場合最小値を達成できる（適当にswapしたとしてプラマイ0で変化しないので）
あとは3色セットの真ん中に対応させられるのが何個あるのかをそれぞれ求めて掛け合わせる

https://atcoder.jp/contests/agc037/submissions/10123166

E - Black or White

黒だけ, 白だけになる確率をそれぞれ求めればよい

https://atcoder.jp/contests/exawizards2019/submissions/10163359

C - Domino Quality

aacd
bbcd
efgg
efhh

aabbc
dee.c
d..fg
h..fg
hiijj

aabc..
ddbc..
..aabc
..ddbc
bc..aa
bc..dd

aabbcc.
dd.dd.a
..d..da
..d..db
dd.dd.b
..d..dc
..c..cc

これを対角線で並べると全行・全列のクオリティが3

E - Avoiding Collision

最短経路数を数えるのは最短路DAGを考えればDPすればできる
各頂点，辺について衝突するパターンが何通りあるか数えて引く

https://atcoder.jp/contests/arc090/submissions/10167547

F - Infinite Sequence

1, 2 1 1, 3 1 1 1, 4 1 1 1 1, … のように1が並んだ後に1の個数以下の数がくるような並びで分割できる
$\text{dp} \lbrack i \rbrack = \lbrack i,\infty)$ が何通りか
$\text{dp} \lbrack i \rbrack = (n-1)^2 + \text{dp} \lbrack i+1 \rbrack + \sum_{j=2}^n \text{dp} \lbrack i+j+1 \rbrack$
$(n-1)^2$ → $x y y \ldots (x,y \neq 1)$ となるパターン
$\text{dp} \lbrack i+1 \rbrack$ → $i$ 番目が1ならば $i+1$ 番目まではなんでもok
$\sum_{j=2}^n \text{dp} \lbrack i+j+1 \rbrack$ → $i$ 番目が $x \gt 1$ でそれ以降に1が $x$ 個並ぶパターン

ちゃんともれなくダブりなく数え上げるのが大事
https://atcoder.jp/contests/arc071/submissions/10206796

D - Reversed LCS

dp[l][r][i] = 部分文字列[l,r]をi回まで変化させたときの答え
遷移は4通り

chmax(dp[l-1][r][i], dp[l][r][i])
chmax(dp[l][r+1][i], dp[l][r][i])
chmax(dp[l-1][r+1][i], dp[l][r][i]+2) s[l-1]==s[r+1]
両端が一致するならそこで+2
chmax(dp[l-1][r+1][i+1], dp[l][r][i]+2)
両端が一致しなくても変化させれば+2できる

https://atcoder.jp/contests/agc021/submissions/10211919

E - Product of Arithmetic Progression

P(a/d+n-1, n) * dⁿ が答え
a/d+n-1 がMOD以上になる場合やd=0の場合に注意

https://atcoder.jp/contests/m-solutions2019/submissions/10223087

E - Bichromization

隣接する重みが同じ頂点対については隣接する辺をつかって頂点重みを達成できる
このような頂点からスタートして重みが増加するような頂点へ遷移することはできる
多点BFSみたいなのをするとできる

E - Bichrome Tree

vを根とする部分木についてvと異なる色にする頂点の重みの和はできるだけ小さい方がよい
子孫の重みが小さい分には重みを増やせばいいので調整できるが，大きいとどうしようもないので
したがって各頂点について条件を満たすような重みにしたとき，異なる色の重みを最小化する問題を木DPで再帰的に解いていく

各子について色をあわせるか/合わせないか2通りがある
dp[i番目まで][頂点vと同じ色の重みがj以下] = 異なる色の最小
としたDPを各頂点で解くと，異なる色の重みの最小化ができる

https://atcoder.jp/contests/arc083/submissions/10256207

E - Young Maids

辞書順なので貪欲に考える
先頭になりうるのは偶数番目の要素なのでこの中でもっとも小さい要素が先頭
2番目になりうるのは先頭より後かつ奇数番目
区間[3番目の位置,4番目の位置]が先頭,2番目の要素を含むようなのは無理なので，[0,1番目の位置) [1番目の位置+1, 2番目の位置) [2番目の位置+1, n) と区間を分割して，区間内で考えるようにする

これを普通に書くと $O(n^2)$ なので高速化する
区間を選択するパートと区間の中から偶数/奇数番目の最小の要素を見つけるパートが存在する
最小の要素を見つけるのはセグ木2本持てばok
区間を選択するパートはkeyとしてその区間の偶数番目の最小の要素をもたせたヒープをもつとできる

セグ木で高速化しようとしたけどデータの持ち方が微妙で実装が終了した

https://atcoder.jp/contests/arc080/submissions/10323584

D - Black and White Tree

葉に隣接する頂点に白を置いたら葉に黒を置かないと不可能
相手を強制できる操作はだいたい強い[要出典]のでこれを繰り返す
葉と葉に隣接する頂点を消すのを繰り返したときに孤立点が残ってたらそこを白にできる
トポソみたいな雰囲気で葉から消してく操作を繰り返す

解説を読んで証明をかんがえる
完全マッチングが存在 → 白を置いた頂点に対応する頂点に黒を置けば後攻の勝ち
完全マッチングが存在しない
葉に隣接する頂点を白にしたとき，葉は絶対に黒に塗らないといけない
この2頂点を取り除いたn-2頂点の木の問題に帰着できる
完全マッチングが存在しないので確実に1頂点は残るので先行の勝ち

https://atcoder.jp/contests/agc014/submissions/10325854

E - Non-triangular Triplets

とりあえず $c_i$ にするのは $k+2n \sim k+3n-1$
kからk+2n-1までの和 <= k+2nからk+3n-1までの和じゃないと明らかに不可能

k+n/2番目までを大きい方に対応させるとなんかうまくいく
a: 1 2 3 4 / 5 6 7
b: 11 12 13 14 / 8 9 10
c: 12 14 16 18 / 13 15 17

天才構築があったことだけ覚えててがちゃがちゃやってたら見つかった

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/10327229

E - Papple Sort

回文にできるかの判定はいつもの

文字列の前半・後半で半分ずつに分割されてないと回文になるわけがないのでとりあえずこれを満たすようにする
あと文字列長が奇数なら真ん中の1文字は奇数個のやつ

同じ文字を入れ替える意味はないので，各文字種ごとに前半分と真ん中にくるやつと後ろ半分に分割
最短手数でこれを満たす文字列をつくる
ataatmma → atamatma

後ろ半分をswapしても前半分をswapしても結局関係ない
後ろ半分を前半分に合わせることにする
atamatma → atammata

与えられた文字列のi番目をtrans[i]番目に持っていくべきというのがわかる
あとは普通の転倒数を求めるだけ

https://atcoder.jp/contests/arc088/submissions/10330482

E - Snuke Line

調和級数っぽい

FOR(d, 1, m+1) for(int i=d; i<=m; i+=d) {  
    // (i-d, i] に始点がある && (i-d, i] に終点がない区間を数える  
    // rangefreqができるやつで頑張る  
}

segtreeとかwaveletで数えたら間に合ったけどこれ計算量なんだ
segtreeは $O(M \log M \log^2 N)$ とかに見えるけど1secで通った
実はもうちょっと早いのか…？

https://atcoder.jp/contests/arc068/submissions/10331633

解説を見た
区間長がd以上 → 必ず訪れる
それ以外 → 高々1回しか訪れることはない
1回しか訪れない区間に一様に+1した数列をつくっておく
この数列で添字がdの倍数のところを見て和を求めると答えが求まる

dを増やしたときに区間長がd未満になる → 数列の[l,r]に+1
あとは各dについて倍数のところだけ見ると調和級数

https://atcoder.jp/contests/arc068/submissions/10332345

C - Median Sum

部分和問題なのでDPするしかない
とりあえず思いつくのはdp[i番目まで][和がj以下] = 何通り
これは $O(N^2A)$ あっておしまい

部分集合Pとその補集合Qのペアをつくる
sum(P) <= sum(Q) としても一般性を失わない
sum(P) + sum(Q) = 全体の和なので sum(P) <= 和/2 <= sum(Q)

部分集合の和の前半部分の $2^{N-1}$ 個にP，後半部分にQが対応する
中央値となるのはQのうち一番小さいものになる
dp[i番目まで][和をjにできるか] = true/false としたDPをする
これはbitsetで高速化できて $O(N^2A/64)$ ならok

bitsetで荒れた（？）のおぼえてる

https://atcoder.jp/contests/agc020/submissions/10332780

C - Three Circuits

場合分けして頑張る

次数が奇数の頂点が存在
一筆書きで一周することがそもそも不可能なので無理
次数が6以上の頂点vが存在
頂点vからスタートして一筆書きをする
頂点vに訪れるたびにサーキットとして分割すると少なくとも3個には分割できる
次数が4の頂点が1個以下
一つサーキットをつくるには各頂点から次数2減らす分の辺が少なくとも必要なのでどう頑張っても足りない
次数が4の頂点が3個以上
次数4の頂点をA,B,Cとする
Aを始点として一筆書きをすると，次数が6以上の場合と同様の議論で少なくとも2つのサーキットに分割可能
- サーキットの少なくとも1つに2回以上訪れる頂点が存在
  その頂点のところでサーキットを切断すると，サーキットを増やせる
- それ以外
  A → … → B → … → C → … → A みたいなサーキットが2つ存在する
  A → B, B → C, C → A の部分をそれぞれつなぎ合わせるとサーキットができるので3個つくれる
次数4の頂点が2個
次数4の頂点をA,Bとする
AとBの間の経路が2本 → OK
AとBの間の経路が4本 → NG

証明が大変

https://atcoder.jp/contests/agc032/submissions/10341260

E - Awkward Response

桁数が同じ場合，辞書順と昇順は一致するのでとりあえず桁数を求めたくなる
1, 10, 100, … と答えを比較してみる
答えを123とする
1 → 'Y' 1<=123, str(1)<=str(123)
10 → 'Y' 10<=123, str(10)<=str(123)
100 → 'Y' 100<=123, str(100)<=str(123)
1000 → 'N' 1000>123, str(1000)<=str(123)
10000 → 'N' 10000>123, str(10000)<=str(123)
Yが返される最大の桁数と一致する

答えが 100…00 の場合，任意の $10^a$ についてYが返ってくるので上の方法で桁数を求めようとしてもうまくいかない
このパターンについては9…99を試せばいいのでok

残りのパターンについては

n < N のとき: str(10n) <= str(N), 10n > N なので'N'が返り値
n >= N のとき: str(10n) > str(N), 10n > N なので'Y'が返り値

となる単調性を使って二分探索

https://atcoder.jp/contests/arc078/submissions/10343490

F - Sum Difference

S+T = sum(A_i) で一定
S-T = sum(A_i) - 2T なので T が取りうる値が何通りか求めればよい

数列からi個選んだときに作れる数は $ix + d(0+1+…+i) \sim ix + d{(n-i)+(n-i+1)+…+(n-1)}$ の範囲になる
0~n-1の中から自由にi個選んだとき $0+1+…+i \sim (n-i)+(n-i+1)+…+(n-1)$ の範囲は全部作れる
ix mod d で場合分けするとある連続した区間を全部つくれることになる
あとは区間がたくさん与えられたときの和集合の大きさを求められればよい
区間を始点でソートして手前からマージしていけばok

D - Isomorphism Freak

カラフルさの最小化から考える
木の直径の中心をもとに対称になるような木をつくると ceil(木の直径/2) はできそう
ceil(木の直径/2) より小さくするのは無理そう

ceil(木の直径/2) を達成するように中心を設定したときの葉の枚数を考える
対称となるような木にするため設定した中心を根にしたときの，各深さでの頂点数の積となる

各頂点・辺を中心としたときの葉の枚数をすべて試すことで $O(n^2)$

https://atcoder.jp/contests/agc024/submissions/10358491

C - Squared Graph

連結成分ごとに考えていく
パリティ的に二部グラフ・非二部グラフで連結成分の数が変わるのがわかる
二部と二部をつなぐ → 連結成分2つ
非二部と何かをつなぐ → 連結成分1つ
孤立点と何かをつなぐ → 頂点数分の連結成分

二部グラフ判定をバグらせない

https://atcoder.jp/contests/agc011/submissions/10370738

C - GP 2

操作によってできる数列がどのようなものか考える
明らかな必要条件として

合計が3M
max < 2M
奇数はM個以下

これを満たすような数列ならつくれることが確認できてこれは必要十分条件

とりあえずmax < 2M の条件を忘れて，別の条件を満たすやつを数える
これは N要素の数列 && 合計が3M && 奇数がM個以下を数えれば良い
奇数がi個のとき → (奇数の場所i個の選び方) * (総和が3M-iとなる偶数からなる数列の総数)
(奇数の場所i個の選び方) = combi(n, i)
(総和が3M-iとなる偶数からなる数列の総数)
= (総和が(3M-i)/2となる数列の総数)
= combi( (3M-i)/2+N-1, N-1)
0 <= i <= min(N,M) について求めて足すことで求められる
よってこれは O(N+M) で求められた

max >= 2M となるようなものを引く
N-1要素の数列 && 合計がM以下 && 奇数がM個以下となる数列に 3N-合計の要素を足すとmax >= 2M の数列になる
要素を足す位置はN通り存在するので，ありえる数列の総数にNを掛ければok
(N-1要素の数列 && 合計がM以下 && 奇数がM個以下となる数列の総数)
= (N要素の数列, 合計がM, 奇数がM個以下) - (N-1要素の数列, 合計がM, 奇数がM個以下)

これらの数列は上記の数列と同様に求められる

https://atcoder.jp/contests/agc036/submissions/10374598

F - Colorful Tree

求める距離 = (パスu,vの距離) - (色xの辺の距離) + (色xの辺の本数)y
パスu-vの距離 = (根からuの分) + (根からvの分) - 2(根からlcaの分) と分割する

各頂点にクエリ番号idxのLCAかパスの端点か？の情報をもたせておく
根から今いる頂点までのパスについての距離・色ごとの本数・色ごとの距離を持ちながら木上を移動していき，各頂点に来たときに対応するクエリに寄与する分を計算

https://atcoder.jp/contests/abc133/submissions/10376688

F - Xor Sum 3

X = A_1 xor A_2 xor … xor A_n とする
Xが1となる，つまり1が奇数個の桁についてはどう分割しても赤のXOR + 青のXOR が1にしかならない
Xが0の桁については (赤のXOR, 青のXOR) が (0, 0) か (1, 1) になる
Xが0の桁についてのみ考えると，赤のXORも青のXORも常に同じ
部分集合をうまく選ぶことでXOR和を最大化するような問題になった
これは60×NのF_2の行列とみなして，基底を求めたあと，上の桁から貪欲に大きくしていくことで解ける

https://atcoder.jp/contests/abc141/submissions/10377318

C - Cleaning

こういうのは木DPする
葉について色々する問題で根を葉にすると面倒なのでそうならないようにする
n=2だと全頂点が葉でコーナーになりがちなので注意

頂点vを根とした部分木内で完結するパスと頂点vの親の方へ向かうパスが存在する
各部分木で部分木内のマッチングがうまくできるか？と親の方へ向かうパスが何本か？をボトムアップで解いていく

頂点vの子cについて親へ向かうパスが何本あるか？の情報が伝播されてくる
a[v] と sum(dp[c]) の値から頂点vの親へ向かうパスが何本になるかは一意に定まって，(a[v] - ceil(sum/2))*2 + sum%2 本になる
あとは a[v]-(親へ向かうパスの本数) 個のペアをつくれるか？という問題になる
これは max > sum/2 が必要十分条件で判定可能

https://atcoder.jp/contests/agc010/submissions/10384308

E - XOR Partitioning

累積XORを取るとかなり見通しがよくなる
最初の区間のXORがXとすると，次の区間をXにするには累積XORが0の位置までを次の区間にする必要がある
その次の区間をXにするには累積XORがXの位置までを次の区間にする必要がある
同様に考えると累積XORが X 0 X 0 X 0 … となるような要素を順に選んでいく方法が何通りあるか？という問題に置き換えられた
これはdpを行うことでO(Xと0の個数)で解ける

2²⁰通りのX全てについてdpを行うと0が多い場合にTLEしてしまう
そこで0が連続する場所についてまとめてDPの遷移を行うことで各XについてO(Xの個数)でDPを行うことができる

https://atcoder.jp/contests/diverta2019/submissions/10387058

E - Negative Doubling

負の部分と正の部分に2分割して，それぞれ独立に解く
[0,i] を負で増加列にするのに必要な操作回数・[i,n) を正で増加列にするのに必要な操作回数をそれぞれ求められればあとは全てのiについて試すことで解ける

符号を固定した場合，4倍する操作を繰り返すとみなせる
DPで操作回数を求める
状態： dp1[i][j] = (i番目に4倍する操作をj回行うときに区間[i,n)を昇順にするのに必要な操作回数)
遷移： chmin(dp1[i][j], dp1[i+1][k] + j) ただし $k$ は [tex:a \lbrack i \rbrack 4^j \lt = a \lbrack i+1 \rbrack 4^k] を満たす

負の部分についても同様のDPで解ける

https://atcoder.jp/contests/caddi2018/submissions/10399167

F - Coincidence

y mod x と x xor y が一致するのは最上位bitが同じで(1,0)となる桁が存在しないとき
dp[i桁目][L<=xが確定か？][y<=Rが確定か？][(1,1)がすでに現れたか] で桁DP

D - Teleporter

a[0]=0以外で条件を満たすことはない
a[0]=0とすると，頂点0との距離がK以下となるように辺をつなぎかえる問題になる
木をボトムアップに見ていって，頂点vを根とする部分木に距離Kより遠い頂点が存在するならばつなぎかえるとすればよい

https://atcoder.jp/contests/agc004/submissions/10400747

F - Strange Nim

実験するとgrundy数は
nがk未満なら 0
n%k=0 なら n/k
それ以外なら grundy[n] = grundy[n-n/k-1]
になっている

これを愚直に求めようとするとTLEするのでうまくまとめたい
n/kが小さいときが問題なのでn/kが変わらないうちはまとめて遷移する
n-i(n/k+1) が n/k*k 以下になるようなiの分はまとめて遷移できる
こうすると O(min(N/K, K)) でgrundy数が計算できて間に合う

https://atcoder.jp/contests/arc091/submissions/10401549

E - Ball Coloring

rmin = min, bmax = max もしくは rmin = min, rmax = max の2パターンに分類できる
rmin = min, bmax = max の場合，小さい方を赤，大きい方を青に塗るのが最適
rmin = min, rmax = max の場合，どう塗ってもrmax-rminは変動しないので青は自由に塗ってよい
x[i] < y[i] として x[i] でsortしておく
このとき [0,i] はyを青，[i+1,n) はxを青と塗るのが最善
より小さいxが青くなっているのに，x→yに変えても最大値が大きくなるだけで絶対に得することはない

https://atcoder.jp/contests/arc073/submissions/10403071

F - Strings of Eternity

[i,i+t.size()) が t と一致する場合，グラフの頂点iから頂点(i+t.size()) mod s.size()に有向辺を張る
この有向グラフで最長経路を求めればよい

ループが存在するならば無限に増やせて答えは-1
ループ検出はトポソでできる
ループが存在しないならばDAGなのでDPすれば求まる

https://atcoder.jp/contests/abc135/submissions/10402080

2020-02-18

ABC155 F - Perils in Parallel

AtCoder

問題ページ

まず，各ケーブルについて爆弾 $\lbrack l_i,r_i)$ のスイッチを反転するという形に書き換えておきます．

爆弾のスイッチについて差分XORを取っておくと，区間に一様にXORするという操作は2点にXORを行う操作に帰着できます．この操作を繰り返し行ったときに，値を全て0にできるか？という問題になります．適当にスイッチがオフの爆弾を追加しておけば，爆弾が全部オンで差分XORが全て0になる状況は回避できます．

$\lbrack l_i,r_i)$ に作用するスイッチが存在した場合，頂点 $l_i$ と頂点 $r_i$ を結ぶ辺を追加したグラフを考えます．頂点の値は差分XORを取った値に対応させます．このグラフの辺の部分集合をうまく選び，次数の偶奇と頂点の値を一致させることができるか？という問題に帰着できました．

DFS木を葉からボトムアップで参照していきます．辺 $(v,ch)$ について子 $ch$ の頂点の値が1ならば辺を使用する集合に追加し． $v$ の頂点の値を変化させます．この処理を行ったあと，根以外については条件を満たすようになっています．根の値が0ならば，その連結成分については条件を満たす辺集合のとり方が存在します．根の値が1の場合は条件を満たす辺集合が存在しません．なぜなら，辺を追加することで次数の偶奇が変化する頂点は2つであり，1頂点(根だけ)の次数の偶奇を変更しようとしても，次数が一致している頂点の個数の偶奇が合わないからです．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m;  
    cin >> n >> m;  
    vector<PII> a(n);  
    REP(i, n) cin >> a[i].first >> a[i].second;  
    a.push_back({INF, 0});  
    sort(ALL(a));  
  
    // XOR差分取っておくと2点に対する更新になる  
    vector<ll> x(n+1);  
    REP(i, n+1) x[i] = a[i].second ^ (i==0 ? 0 : a[i-1].second);  
  
    vector<vector<PII>> g(n+1);  
    REP(i, m) {  
        ll l0, r0;  
        cin >> l0 >> r0;  
        // [l, r) の爆弾に作用する  
        ll l = lower_bound(ALL(a), PII(l0, 0)) - a.begin();  
        ll r = upper_bound(ALL(a), PII(r0, 1)) - a.begin();  
        if(l < r) {  
            g[l].emplace_back(r, i);  
            g[r].emplace_back(l, i);  
        }  
    }  
  
    vector<ll> ans;  
    vector<bool> used(n);  
    function<ll(ll,ll)> dfs = [&](ll v, ll p) {  
        used[v] = true;  
        ll ret = x[v];  
        for(auto to: g[v]) {  
            if(to.first != p && !used[to.first]) {  
                ll val = dfs(to.first, v);  
                if(val%2) {  
                    ans.push_back(to.second);  
                    ret ^= 1;  
                }  
            }     
        }  
        return ret;  
    };  
    bool ok = true;  
    REP(i, n) if(!used[i] && dfs(i, -1)==1) ok = false;  
      
    if(!ok) cout << -1 << endl;  
    else {  
        sort(ALL(ans));  
        cout << ans.size() << "\n";  
        REP(i, ans.size()) cout << ans[i]+1 << (i+1==ans.size() ? '\n' : ' ');  
        cout << flush;  
    }  
  
    return 0;  
}

2020-02-18

ABC155 E - Payment

AtCoder

問題ページ

36 を支払うときに価値1の紙幣を使う枚数は「6枚」か「0枚で価値10の紙幣1枚を支払ってお釣りで価値1を4枚もらう」の二択です．このように，各価値の紙幣を使う方法はぴったり同じ枚数を用いるか，一つ上の価値の紙幣を使ってお釣りをもらうかの二択です．

dp[下からi桁目][一つ下の貨幣の支払いで使ったか？] = 紙幣を用いる最小枚数と状態を持ち，下の桁から参照するDPを行うことで数えることができます．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
ll dp[1000001][2];  
int main(void) {  
    string s;  
    cin >> s;  
    ll n = s.size();  
  
    dp[n][1] = INF;   
    for(ll i=n; i>=1; --i) {  
        dp[i-1][0] = dp[i][0] + s[i-1]-'0';  
        chmin(dp[i-1][0], dp[i][1] + s[i-1]-'0'+1);  
        dp[i-1][1] = dp[i][0] + 10-(s[i-1]-'0');  
        chmin(dp[i-1][1], dp[i][1] + 10-(s[i-1]-'0'+1));  
    }  
    cout << min(dp[0][0], dp[0][1]+1) << endl;  
  
    return 0;  
}

2020-02-18

ABC155 D - Pairs

AtCoder

問題ページ

$K$ 番目の数が $X$ 以上か？という判定問題に単調性が存在することから，こうした問題では $K$ 番目の数を決め打つ二分探索を行うのが常套手段です．

「 $K$ 番目の数が $X$ 以上か？」という問題は「 $X$ 未満の数が $K-1$ 個以下か？」と言い換えることができます． $A_i$ を固定したときに $A_iA_j \lt X$ となる $A_j$ が何個存在するかを数えます．

$A_i$ の正負で場合分けしてそれぞれ尺取り法を用いることで数えます．

$A_i \lt 0, A_j \lt 0$
$j$ が大きくなるにつれて $A_iA_j$ は小さくなります．したがって条件を満たす $j$ は区間 $\lbrack k,sz)$ に属します．また， $i$ を大きくした場合 $A_iA_j$ は小さくなるため， $k$ は小さくなる方向に動きます． $i$ に対応する $k$ を保持するように尺取法を行うことで答えを求められます．
$A_i \lt 0, A_j \geq 0$
$A_i \geq 0, A_j \lt 0$
$A_i \geq 0, A_j \geq 0$
他の3パターンについても同様に尺取法で数えられます．

同じ要素を選ぶことはできないことに注意が必要です． $i \lt j$ となるペアだけを数えるのではなく，あとで2で割るようにすると実装が楽です．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, k;  
    cin >> n >> k;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
    sort(ALL(a));  
  
    vector<ll> plus, minus;  
    REP(i, n) {  
        if(a[i]<0) minus.push_back(a[i]);  
        else plus.push_back(a[i]);  
    }  
  
    // K番目がmid以上である → X未満がK-1個以下である  
    auto check = [&](ll x) {  
        ll num = 0;  
        ll idx1 = (ll)minus.size()-1, idx2 = 0;  
        REP(i, minus.size()) {  
            while(idx1 >= 0 && minus[i]*minus[idx1]<x) idx1--;  
            while(idx2 < (ll)plus.size() && minus[i]*plus[idx2]>=x) idx2++;  
            num += (ll)minus.size() - idx1 - 1;  
            if(idx1 < i) num--;  
            num += (ll)plus.size() - idx2;  
        }  
        idx1 = 0, idx2 = (ll)plus.size()-1;  
        REP(i, plus.size()) {  
            while(idx1 < (ll)minus.size() && plus[i]*minus[idx1]<x) idx1++;  
            while(idx2 >= 0 && plus[i]*plus[idx2]>=x) idx2--;  
            num += idx1;  
            num += idx2+1;  
            if(i <= idx2) num--;  
        }  
        return num/2 <= k-1;  
    };  
  
    ll lb = -INF, ub = INF;  
    while(ub-lb>1) {  
        ll mid = (lb+ub)/2;  
        if(check(mid)) lb = mid;  
        else ub = mid;  
    }  
    cout << lb << endl;  
  
    return 0;  
}

2020-02-11

みんなのプロコン 2018 D - XOR XorY

AtCoder

問題ページ
$N$ 個の整数から選ぶ部分をとりあえず無視して， $K \times K$ の表に対して条件を満たす数列 $B$ を考えます．まず，数列の先頭を0で固定してしまいます．先頭を0にしたとき，数列の先頭以外の部分については， $A_{1,2}, A_{1,3}, \ldots, A_{1,K}$ でかかる条件から二択しかありえません． $B_i = 0 \oplus A_{1,i} \oplus X$ もしくは $B_i = 0 \oplus A_{1,i} \oplus Y$ となります．先頭を0以外に固定した場合も同様に2通りに限定できます．

このように数列 $B$ を決めたときに表の残りの部分についての条件を満たすか？を考えます． $B_i, B_j$ について2択が2つで4パターンがあります．

$B_i \oplus B_j = A_{1,i} \oplus A_{1,j} = A_{i,j} \oplus X$
$B_i \oplus B_j = A_{1,i} \oplus A_{1,j} \oplus X \oplus Y = A_{i,j} \oplus X$
$B_i \oplus B_j = A_{1,i} \oplus A_{1,j} = A_{i,j} \oplus Y$
$B_i \oplus B_j = A_{1,i} \oplus A_{1,j} \oplus X \oplus Y = A_{i,j} \oplus Y$

いずれについても $A_{1,i} \oplus A_{1,j} \oplus A_{i,j}$ が $X,Y$ のどちらかであれば条件を満たします．もし条件を満たさない $B_i,B_j$ があれば答えは0です．逆にこの条件を全て満たすならば，2択のどちらを選んでも数列全体として問題の条件を満たします．

先頭を固定する方法 $O(\max(x_i))$ 通りにそれぞれついて，ありうる数列が何通りあるか考えます．先頭を固定したとき， $B_i$ は $X$ とXORを取るか， $Y$ とXORを取るかの二択です．この二択のペア $(i, i \oplus X \oplus Y)$ がそれぞれ何個あるかを数えます．ペア $(i, i \oplus X \oplus Y)$ が $C$ 個あるときに， $i$ を $j$ 個， $i \oplus X \oplus Y$ を $C-j$ 個使う方法は $\binom{C}{j}$ 通りです．各ペアについて何通り存在するか求め，総積を取ることでその先頭で何通り存在するかがわかります．全ての先頭を試し，総和を取ることで答えが求まります．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
template<ll MOD>  
struct modint {  
    ll x;  
    modint(): x(0) {}  
    modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}  
    static constexpr ll mod() { return MOD; }  
    // e乗  
    modint pow(ll e) {  
        ll a = 1, p = x;  
        while(e > 0) {  
            if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}  
            else {a = (a*p) % MOD; e--;}  
        }  
        return modint(a);  
    }  
    modint inv() const {  
        ll a=x, b=MOD, u=1, y=1, v=0, z=0;  
        while(a) {  
            ll q = b/a;  
            swap(z -= q*u, u);  
            swap(y -= q*v, v);  
            swap(b -= q*a, a);  
        }  
        return z;  
    }  
    // Comparators  
    bool operator <(modint b) { return x < b.x; }  
    bool operator >(modint b) { return x > b.x; }  
    bool operator<=(modint b) { return x <= b.x; }  
    bool operator>=(modint b) { return x >= b.x; }  
    bool operator!=(modint b) { return x != b.x; }  
    bool operator==(modint b) { return x == b.x; }  
    // Basic Operations  
    modint operator+(modint r) const { return modint(*this) += r; }  
    modint operator-(modint r) const { return modint(*this) -= r; }  
    modint operator*(modint r) const { return modint(*this) *= r; }  
    modint operator/(modint r) const { return modint(*this) /= r; }  
    modint &operator+=(modint r) {  
        if((x += r.x) >= MOD) x -= MOD;  
        return *this;  
    }  
    modint &operator-=(modint r) {  
        if((x -= r.x) < 0) x += MOD;  
        return *this;  
    }  
    modint &operator*=(modint r) {  
    #if !defined(_WIN32) || defined(_WIN64)  
        x = x * r.x % MOD; return *this;  
    #endif  
        unsigned long long y = x * r.x;  
        unsigned xh = (unsigned) (y >> 32), xl = (unsigned) y, d, m;  
        asm(  
            "divl %4; \n\t"  
            : "=a" (d), "=d" (m)  
            : "d" (xh), "a" (xl), "r" (MOD)  
        );  
        x = m;  
        return *this;  
    }  
    modint &operator/=(modint r) { return *this *= r.inv(); }  
    // increment, decrement  
    modint operator++() { x++; return *this; }  
    modint operator++(signed) { modint t = *this; x++; return t; }  
    modint operator--() { x--; return *this; }  
    modint operator--(signed) { modint t = *this; x--; return t; }  
    // 平方剰余のうち一つを返す なければ-1  
    friend modint sqrt(modint a) {  
        if(a == 0) return 0;  
        ll q = MOD-1, s = 0;  
        while((q&1)==0) q>>=1, s++;  
        modint z=2;  
        while(1) {  
            if(z.pow((MOD-1)/2) == MOD-1) break;  
            z++;  
        }  
        modint c = z.pow(q), r = a.pow((q+1)/2), t = a.pow(q);  
        ll m = s;  
        while(t.x>1) {  
            modint tp=t;  
            ll k=-1;  
            FOR(i, 1, m) {  
                tp *= tp;  
                if(tp == 1) { k=i; break; }  
            }  
            if(k==-1) return -1;  
            modint cp=c;  
            REP(i, m-k-1) cp *= cp;  
            c = cp*cp, t = c*t, r = cp*r, m = k;  
        }  
        return r.x;  
    }  
  
    template<class T>  
    friend modint operator*(T l, modint r) { return modint(l) *= r; }  
    template<class T>  
    friend modint operator+(T l, modint r) { return modint(l) += r; }  
    template<class T>  
    friend modint operator-(T l, modint r) { return modint(l) -= r; }  
    template<class T>  
    friend modint operator/(T l, modint r) { return modint(l) /= r; }  
    template<class T>  
    friend bool operator==(T l, modint r) { return modint(l) == r; }  
    template<class T>  
    friend bool operator!=(T l, modint r) { return modint(l) != r; }  
    // Input/Output  
    friend ostream &operator<<(ostream& os, modint a) { return os << a.x; }  
    friend istream &operator>>(istream& is, modint &a) {   
        is >> a.x;  
        a.x = ((a.x%MOD)+MOD)%MOD;  
        return is;  
    }  
    friend string to_frac(modint v) {  
        static map<ll, PII> mp;  
        if(mp.empty()) {  
            mp[0] = mp[MOD] = {0, 1};  
            FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) {  
                mp[(modint(i) / j).x] = {i, j};  
            }  
        }  
        auto itr = mp.lower_bound(v.x);  
        if(itr != mp.begin() && v.x - prev(itr)->first < itr->first - v.x) --itr;  
        string ret = to_string(itr->second.first + itr->second.second * ((int)v.x - itr->first));  
        if(itr->second.second > 1) {  
            ret += '/';  
            ret += to_string(itr->second.second);  
        }  
        return ret;  
    }  
};  
using mint = modint<1000000007>;  
  
// 前計算O(N) クエリO(1)  
mint combi(ll N, ll K) {  
    const int maxN=5e5; // !!!  
    static mint fact[maxN+1]={},factr[maxN+1]={};  
    if (fact[0]==0) {  
        fact[0] = factr[0] = 1;  
        FOR(i, 1, maxN+1) fact[i] = fact[i-1] * i;  
        factr[maxN] = fact[maxN].inv();  
        for(ll i=maxN-1; i>=0; --i) factr[i] = factr[i+1] * (i+1);  
    }  
    if(K<0 || K>N) return 0; // !!!  
    return factr[K]*fact[N]*factr[N-K];  
}  
  
int main(void) {  
    ll n, m, x, y;  
    cin >> n >> m >> x >> y;    
    vector<ll> v(n);  
    REP(i, n) cin >> v[i];  
    vector<vector<ll>> a(m, vector<ll>(m));  
    REP(i, m) REP(j, m) cin >> a[i][j];  
  
    bool flag = true;  
    REP(i, m) REP(j, m) {  
        ll t = a[i][j] ^ a[0][i] ^ a[0][j];  
        if(t != x && t != y) flag = false;  
    }  
  
    if(!flag) {  
        cout << 0 << endl;  
        return 0;  
    }  
  
    const ll sz = 2048;  
    vector<ll> cntv(sz);  
    REP(i, n) cntv[v[i]]++;  
  
    // 先頭は (i, i^x^y) の二択  
    set<PII> st;  
    mint ret = 0;  
    REP(i, sz) {  
        PII p = minmax(i, i^x^y);  
        if(cntv[i] == 0 || st.find(p) != st.end()) continue;  
        st.insert(p);  
        // 先頭を決めたときに使うペアをカウント  
        vector<ll> cnta(sz);  
        cnta[min(i, i^x^y)]++;  
        FOR(j, 1, m) cnta[min(a[0][j]^i^x, a[0][j]^i^y)]++;  
        // ペアごとに何通りあるか数える  
        mint prod = 1;  
        REP(j, sz) {  
            if(cnta[j] == 0) continue;  
            mint sum = 0;  
            REP(k, cnta[j]+1) if(cntv[j]>=k && cntv[j^x^y]>=cnta[j]-k) sum += combi(cnta[j], k);  
            prod *= sum;  
        }  
        ret += prod;  
    }  
    cout << ret << endl;  
  
    return 0;  
}

2020-02-08

SoundHound Programming Contest 2018 Masters Tournament 本戦 C - Not Too Close

AtCoder

問題ページ

考えたこと

長さ $D$ のパスグラフを作ったあと、 $D$ 未満の経路ができないように辺をつなぐみたいな感じで考えてた
ラベルを無視して数え上げたあと頂点にラベルをつければいいかと思ったら、ラベルをつけるパートが大変でダブらずに数える方法が何もわからなくて終了
ラベルを無視していいなら包除っぽく最短距離が $X$ 以下になるやつを数えていけばできると思ったんだけど、合ってるかはわからん

解法

頂点1からの距離でグラフを層に分解してDPをします。 $\text{dp} \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack = ($ 距離 $i$ までで残り頂点が $j$ で距離 $i$ の頂点が $k$ 個 $)$ とします。DPの遷移は距離 $i+1$ で頂点を $l$ 個使用するとすると、 $\text{dp} \lbrack i+1 \rbrack \lbrack j-l \rbrack \lbrack l \rbrack = \text{dp} \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack \times \binom{j-1}{l} \times 2^{l(l-1)/2} \times (2^k-1)^l$ となります。

$\binom{j-1}{l}$
残りの $j-1$ 個から使用する $l$ 個を取り出す方法
頂点2は最後まで取っておかないといけないので $j-1$ 個
$2^{l(l-1)/2}$
新たに使用する $l$ 個の間の辺を張る方法
$(2^k-1)^l$
$l$ 個の頂点が距離 $i$ のいずれかの頂点と結ばれる方法
距離 $i$ の全ての頂点と結ばれない方法はだめなので-1

このDPで距離が $D-1$ のところまで計算を行い、残りの頂点(2を含む)をどのようにつなげるか計算します。これは $\sum \text{dp} \lbrack d-1 \rbrack \lbrack i \rbrack \lbrack j \rbrack \times (2^j-1) \times (2^{j})^{i-1} \times 2^{i(i-1)/2}$ で計算できます。

$2^j-1$
頂点2を距離 $D-1$ の頂点とつなげる方法
$(2^{j})^{i-1}$
2以外の残っている頂点を距離 $D-1$ の頂点とつなげる方法
必ずしも繋げる必要はないので-1はいらない
$2^{i(i-1)/2}$
残っている頂点同士を結ぶ方法

感想

解説見て遷移考えてDP書いたら $i=D-1$ でだいぶハマった

ToDo: グラフが与えられたときに、ラベル付きグラフとして同型なものは重複してカウントしない条件で、ラベルの付け方が何通りあるか求めるのって可能なのか…？
ラベルをつけるのが難しい(のか？)と知っていればDPなり全探索系をするしかないと思えそう

層ごとに分割することで一つ前の層だけを見ればよくなって、DPできるようになるパターンは覚えておくべきっぽい

#include <bits/stdc++.h>    
using namespace std;    
using ll = long long;    
using PII = pair<ll, ll>;    
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)    
#define REP(i, n) FOR(i, 0, n)    
#define ALL(x) x.begin(), x.end()    
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }    
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }    
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;    
#ifdef DEBUG_     
#include "../program_contest_library/memo/dump.hpp"    
#else    
#define dump(...)    
#endif    
const ll INF = 1LL<<60;  
  
template<ll MOD>  
struct modint {  
    ll x;  
    modint(): x(0) {}  
    modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}  
    static constexpr ll mod() { return MOD; }  
    // e乗  
    modint pow(ll e) {  
        ll a = 1, p = x;  
        while(e > 0) {  
            if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}  
            else {a = (a*p) % MOD; e--;}  
        }  
        return modint(a);  
    }  
    modint inv() const {  
        ll a=x, b=MOD, u=1, y=1, v=0, z=0;  
        while(a) {  
            ll q = b/a;  
            swap(z -= q*u, u);  
            swap(y -= q*v, v);  
            swap(b -= q*a, a);  
        }  
        return z;  
    }  
    // Comparators  
    bool operator <(modint b) { return x < b.x; }  
    bool operator >(modint b) { return x > b.x; }  
    bool operator<=(modint b) { return x <= b.x; }  
    bool operator>=(modint b) { return x >= b.x; }  
    bool operator!=(modint b) { return x != b.x; }  
    bool operator==(modint b) { return x == b.x; }  
    // Basic Operations  
    modint operator+(modint r) const { return modint(*this) += r; }  
    modint operator-(modint r) const { return modint(*this) -= r; }  
    modint operator*(modint r) const { return modint(*this) *= r; }  
    modint operator/(modint r) const { return modint(*this) /= r; }  
    modint &operator+=(modint r) {  
        if((x += r.x) >= MOD) x -= MOD;  
        return *this;  
    }  
    modint &operator-=(modint r) {  
        if((x -= r.x) < 0) x += MOD;  
        return *this;  
    }  
    modint &operator*=(modint r) {  
    #if !defined(_WIN32) || defined(_WIN64)  
        x = x * r.x % MOD; return *this;  
    #endif  
        unsigned long long y = x * r.x;  
        unsigned xh = (unsigned) (y >> 32), xl = (unsigned) y, d, m;  
        asm(  
            "divl %4; \n\t"  
            : "=a" (d), "=d" (m)  
            : "d" (xh), "a" (xl), "r" (MOD)  
        );  
        x = m;  
        return *this;  
    }  
    modint &operator/=(modint r) { return *this *= r.inv(); }  
    // increment, decrement  
    modint operator++() { x++; return *this; }  
    modint operator++(signed) { modint t = *this; x++; return t; }  
    modint operator--() { x--; return *this; }  
    modint operator--(signed) { modint t = *this; x--; return t; }  
    // 平方剰余のうち一つを返す なければ-1  
    friend modint sqrt(modint a) {  
        if(a == 0) return 0;  
        ll q = MOD-1, s = 0;  
        while((q&1)==0) q>>=1, s++;  
        modint z=2;  
        while(1) {  
            if(z.pow((MOD-1)/2) == MOD-1) break;  
            z++;  
        }  
        modint c = z.pow(q), r = a.pow((q+1)/2), t = a.pow(q);  
        ll m = s;  
        while(t.x>1) {  
            modint tp=t;  
            ll k=-1;  
            FOR(i, 1, m) {  
                tp *= tp;  
                if(tp == 1) { k=i; break; }  
            }  
            if(k==-1) return -1;  
            modint cp=c;  
            REP(i, m-k-1) cp *= cp;  
            c = cp*cp, t = c*t, r = cp*r, m = k;  
        }  
        return r.x;  
    }  
  
    template<class T>  
    friend modint operator*(T l, modint r) { return modint(l) *= r; }  
    template<class T>  
    friend modint operator+(T l, modint r) { return modint(l) += r; }  
    template<class T>  
    friend modint operator-(T l, modint r) { return modint(l) -= r; }  
    template<class T>  
    friend modint operator/(T l, modint r) { return modint(l) /= r; }  
    template<class T>  
    friend bool operator==(T l, modint r) { return modint(l) == r; }  
    template<class T>  
    friend bool operator!=(T l, modint r) { return modint(l) != r; }  
    // Input/Output  
    friend ostream &operator<<(ostream& os, modint a) { return os << a.x; }  
    friend istream &operator>>(istream& is, modint &a) {   
        is >> a.x;  
        a.x = ((a.x%MOD)+MOD)%MOD;  
        return is;  
    }  
    friend string to_frac(modint v) {  
        static map<ll, PII> mp;  
        if(mp.empty()) {  
            mp[0] = mp[MOD] = {0, 1};  
            FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) {  
                mp[(modint(i) / j).x] = {i, j};  
            }  
        }  
        auto itr = mp.lower_bound(v.x);  
        if(itr != mp.begin() && v.x - prev(itr)->first < itr->first - v.x) --itr;  
        string ret = to_string(itr->second.first + itr->second.second * ((int)v.x - itr->first));  
        if(itr->second.second > 1) {  
            ret += '/';  
            ret += to_string(itr->second.second);  
        }  
        return ret;  
    }  
};  
using mint = modint<1000000007>;  
  
// 前計算O(N) クエリO(1)  
mint combi(ll N, ll K) {  
    const int maxN=5e5; // !!!  
    static mint fact[maxN+1]={},factr[maxN+1]={};  
    if (fact[0]==0) {  
        fact[0] = factr[0] = 1;  
        FOR(i, 1, maxN+1) fact[i] = fact[i-1] * i;  
        factr[maxN] = fact[maxN].inv();  
        for(ll i=maxN-1; i>=0; --i) factr[i] = factr[i+1] * (i+1);  
    }  
    if(K<0 || K>N) return 0; // !!!  
    return factr[K]*fact[N]*factr[N-K];  
}  
  
mint dp[50][50][50];  
signed main() {  
    ll n, d;  
    cin >> n >> d;  
  
    vector<mint> pw2(1000);  
    pw2[0] = 1;  
    FOR(i, 1, 1000) pw2[i] = pw2[i-1] * 2;  
  
    dp[0][n-1][1] = 1;  
    REP(i, d-1) FOR(j, 1, n+1) REP(k, n+1) {  
        if(dp[i][j][k] == 0) continue;  
        mint p = pw2[k]-1;  
        FOR(l, 1, j+1) {  
            dp[i+1][j-l][l] += dp[i][j][k] * combi(j-1, l) * pw2[l*(l-1)/2] * p;  
            p *= pw2[k]-1;  
        }  
    }  
  
    mint ret = 0;  
    // 距離d-1の頂点がj個 残りがi個  
    // 2とつなげる方法が 2^j-1  
    // 2以外とつなげる方法が 2^j^i  
    // 残り分をつなげる方法が 2^(i*(i-1)/2)  
    FOR(i, 1, n+1) FOR(j, 1, n+1) ret += dp[d-1][i][j] * (pw2[j]-1) * pw2[j].pow(i-1) * pw2[i*(i-1)/2];  
    cout << ret << endl;  
  
    return 0;  
}