2020年2月24日数学剰余,競プロ,べき乗,ダブリング,繰り返し二乗法,2進数,bit演算

多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。

Input : pow(2,4) (x=2, n=4)
Output : 16

べき乗は非常に大きな数値に ...

2020年2月22日動的計画法bit演算,動的計画法,bitDP,DP,テーマ記事,競プロ

競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。

ビットDPとは

ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...

2020年1月25日AtCoder600点,bit演算,bit全探索,包除原理,,余事象,制約

問題へのリンク

問題概要

N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか?

制約 i:頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上に、黒く塗られた辺が1つ ...

2019年11月22日探索再帰関数,bit演算

ビット全探索とは

bit演算を上手く用いると、それぞれの要素に対して「使うか」「使わないか」の2通りがあるような、\(2^n\) 通りの場合を全探索することができます。

言い換えると、集合 \(\{0,1,2,3,̷ ...