畳み込みやゼータ変換やメビウス変換に関するメモ

書いたライブラリ

fastTransform.cc 

    vector<T> xor_conv(vector<T> vec1, vector<T> vec2);
    vector<T> and_conv(vector<T> vec1, vector<T> vec2);
    vector<T> or_conv(vector<T> vec1, vector<T> vec2);

これらは，{xor|and|or} convolution を返す． vec = xor_conv(vec1, vec2) だったら，vec[k] = \sum {vec1[i] * vec2[j] | i ^ j = k} になる． vec1 や vec2 のサイズは，2の冪乗でなくてはならない．

    void xor_conv_dest(vector<T>& vec1, vector<T>& vec2);
    void and_conv_dest(vector<T>& vec1, vector<T>& vec2);
    void or_conv_dest(vector<T>& vec1, vector<T>& vec2);

これらは，{xor|and|or} convolution を行う．結果は vec1 にセットされる． もとの vec1 と vec2 は両方破壊される． vec1 や vec2 のサイズは，2の冪乗でなくてはならない．

    void hadamard(vector<T>& vec);
    void inv_hadamard(vector<T>& vec);
    void zeta_upper(vector<T>& vec);
    void moebius_upper(vector<T>& vec);
    void zeta_lower(vector<T>& vec);
    void moebius_lower(vector<T>& vec);

これらは，対応する変換を行う．上の畳み込みの関数の内部でも使用されている． 結果は vec にセットされ，元の値は破壊される． vec のサイズは，2の冪乗でなくてはならない． Hadamard 変換は，本来，自分自身が逆変換だが， 関数 hadamard では，定数倍して値が整数になるようにしているので， 定数倍だけ異なる逆変換 inv_hadamard がある．

    int trans_resize(vector<T>& x);

x を，長さが2の冪乗になるように resize する．新しい長さを返す．

    int trans_resize(vector<T>& x, vector<T>& y);

x と y を，長さが同じ2の累乗になるように resize する．新しい長さを返す．

関連する問題

この blog の中の記事

参考になる記事