ビット演算
Sのi番目が1か？
(S >> j) & 1 0-originで0はLSB
要素数Nの全体集合
(1 << N) - 1 補集合(全体集合をUとして)
~S & U rightmost 1
(x & -x) 与えられた集合の要素に対する2重ループ
pythondef calcScore(S):
x = S
ret = 0
i = 0
while x:
if x & 1:
for j in range(i):
if (S >> j) & 1:
ret += M[i, j]
x //= 2
i += 1
return ret与えられた集合の部分集合列挙
pythondef solve(S):
x = S
while x > 0:
print(f"{x:08b}")
x = (x - 1) & STがSに含まれるか？
Sの補集合との共通部分が空
~S & T == 0 1の個数(popcount)
32ビットなら
cT = (T & 0x55555555) + ((T >> 1) & 0x55555555);
T = (T & 0x33333333) + ((T >> 2) & 0x33333333);
T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F);
T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF);
T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF);cT -= (T >> 1) & 0x55555555;
T = (T & 0x33333333) + ((T >> 2) & 0x33333333);
T = (T + (T >> 4)) & 0x0F0F0F0F;
T = (T * 0x01010101) >> 24;
Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →指数時間アルゴリズム×岩田_陽一×巡回セールスマン問題×最大クリーク問題×幅×グリッドグラフ×pathwidth×半分全列挙×最大独立集合問題×fptアルゴリズム×最小頂点被覆問題×有界探索木×カーネライズ×シュタイナー木問題×包除原理×ハミルトンパス×グラフ彩色問題×彩色数×高速ゼータ変換×畳込み×完全マッチングの個数×完全マッチング×color_coding×k-cycle×bandwidth×cut_&_count×iterative_compression→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]