Moamen and XOR

f:id:peroon:20210810075906p:plain

code

void solve(){
  ll n,k;cin>>n>>k;
  
  if(n%2==0){
    // even
    mint sum = 0;

    // & == xor
    // 等号が成り立つ場合の数---
    // equalになる各列
    // 001111
    // 000011
    // などなら、両辺共に0になる
    mint equal = 0;
    for(int i=2; i<=n; i+=2){
      equal += nCr(n,i);
    }
    // それがk列ある
    sum += equal.pow(k);
    // 等号が成り立つ場合の数---ここまで



    // & > xor
    // 大なり分の場合の数---ここから

    // 1列を0にする場合の数
    mint zero_column = 0;
    // 000000
    // 000011
    // 001111 など
    for(int i=2; i<=n; i+=2){
      zero_column += nCr(n,i);
    }

    mint two=2;
    mint free = two.pow(n); // 1列に0,1を自由に置く場合の数は2^n

    mint bigger_sum=0;
    // 何列目でbiggerを確定させるかを全探索
    rep(i,k){
      // i列目でbiggerを確定させる
      
      mint a = zero_column.pow(i); // i-1列までは各列、&もxorも0
      //a *= 1; // i列目は111111で確定
      a *= free.pow(k-i-1); // i+1列以降は自由

      bigger_sum += a;
    }
    
    sum += bigger_sum;
    p(sum.x);
  }
  else{
    // odd

    // equal only

    // 111で1にしてequalにするか
    // 110で0にするか(0の個数が奇数) nC1 + nC3 + ...

    mint a = 1; // 111
    for(int i=1; i<=n; i+=2){ // i:0の個数
      a += nCr(n, i);
    }

    // それがビット数分(k)あるので

    mint ans = a.pow(k);
    p(ans.x);
  }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;

    prepare_nCr();
    
    while(N--)solve();
    
    return 0;
}

other's tweet (C)