C - Coins

atcoder

Quiz

https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_c

観察

  • Kは最大6
  • 32C6 = 906192
  • nCkのパターンを全探索すればいい
  • フラグでnCkを全探索する方法は？
    • next_permutation
    • bit (蟻本 v2 p144)

解法1 全探索 next_permutation

解法2 全探索 bit

  • 蟻本p144にある
ll comb = (1LL<<K) - 1;
while(comb < (1LL<<N)){
    // ここで処理
    
    // フラグ更新
    ll x = comb & -comb, y = comb + x;
    comb = ((comb & ~y) / x >> 1) | y;
}