■A - Not coprime
50以下の素数はたかだか15個なので
bitDPを行う
■B - Special Subsets
unionfindでサイクルの数を求める
2^c-1
■C - Sequence Scores
dpじゃなかった。
根本的に方針が悪かったので解説AC
N*M^Nから余計なものを省く
一旦tleするループを書いて、整理する
ΣΣΣM^(N-(j-i+1))*(M-k-1)^(j-i-1)
をj-iとkの二重シグマに変形し
ΣΣ(N-i)*M^(N-(i+1))*(M-j-1)^(i-1)
区間dpでもできそうだけど無理なのか??
■D - Moving Pieces on Line
未読。
読む気にならなかったです。
■E - Paper Cutting 2
Dよりかはとっつきやすそうでしたが。。
dpでやるには状態数が多すぎるので他の方針を考える必要がある。
各操作が選ばれる確率は、それより後にしか来ない(orやらない)は操作がそれより前に来ない確率になるのでそれの総和
参考:Erasing Vertices(agc49)