【今日の精進】ABC212H - Nim Counting

毎日格上の問題を倒すやつの72日目です。

問題リンク

atcoder.jp

問題概要

山の数が 以下でそれぞれの山の石の個数が に含まれるようなNimのうち、先手が勝てるようなものの個数を求めてね。

解法

要するに、要素のXORが非零であるものの個数を数え上げるという問題です。

実は、Bitwise Xor Convolution とかいうこの問題のために生まれたみたいな畳み込みがあるので、これを使えば、ダブリングの要領で山の個数が2のべき乗のときは求められます。

そしたら、桁DPの要領ですべての和を求めればいけます。

提出コード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

void hadamard(vector<mint> &u){
    int h=1;
    for(int rep=0; rep<16; rep++){
        for(int i=0; i<65536; i+=h*2){
            for(int j=i; j<i+h; j++){
                mint u_j=u[j];
                u[j]+=u[j+h];
                u[j+h]=u_j-u[j+h];
            }
        }
        h=h<<1;
    }
}

vector<mint> xor_comv(vector<mint> u,vector<mint> v){
    hadamard(u);
    hadamard(v);
    for(int i=0; i<65536; i++){
        u[i]*=v[i];
    }   
    hadamard(u);
    for(int i=0; i<65536; i++){
        u[i]/=65536;
    }
    return u;
}

int main(){
    int N,K;
    cin>>N>>K;
    vector<vector<mint>> doub(18,vector<mint>(65536,0));
    for(int i=0; i<K; i++){
        int A;
        cin>>A;
        doub[0][A]=1;
    }
    for(int i=0; i<17; i++){
        doub[i+1]=xor_comv(doub[i],doub[i]);
    }
    vector<mint> lim(65536,0),und(65536,0);
    lim[0]=1;
    for(int i=17; i>=0; i--){
        int j=0;
        for(mint k: xor_comv(und,doub[i])){
            und[j]+=k;
            j++;
        }
        if((N>>i)&1){
            j=0;
            for(mint k:lim){
                und[j]+=k;
                j++;
            }
            lim=xor_comv(lim,doub[i]);
        }
    }
    mint ans=0;
    for(int i=1; i<65536; i++){
        ans+=lim[i]+und[i];
    }
    cout<<ans.val()<<endl;
}

Submission #48061155 - AtCoder Beginner Contest 212

感想

初めて自分で実装した畳み込みがこれですか？