polynomial/with_acl.hpp

• View this file on GitHub
• Last update: 2022-07-17 14:27:07+09:00
• Include: #include "polynomial/with_acl.hpp"

Verified with

• polynomial/test/exp_of_formal_power_series_acl.test.cpp
• polynomial/test/inv_of_formal_power_series_acl.test.cpp
• polynomial/test/log_of_formal_power_series_acl.test.cpp
• polynomial/test/pow_of_formal_power_series_acl.test.cpp

Code

#pragma once

#include <atcoder/convolution>

template <int mod>
class ACLNTT {
public:
    using Mint = atcoder::static_modint<mod>;
    
    static void dft(std::vector<Mint> &a) {
        atcoder::internal::butterfly(a);
    }
    static void idft(std::vector<Mint> &a) {
        atcoder::internal::butterfly_inv(a);
        Mint inv = Mint::raw(a.size()).inv();
        for (Mint &ele : a) {
            ele *= inv;
        }
    }
    static std::vector<Mint> mul(std::vector<Mint> a, std::vector<Mint> b) {
        return atcoder::convolution(a, b);
    }
};

#line 2 "polynomial/with_acl.hpp"

#include <atcoder/convolution>

template <int mod>
class ACLNTT {
public:
    using Mint = atcoder::static_modint<mod>;
    
    static void dft(std::vector<Mint> &a) {
        atcoder::internal::butterfly(a);
    }
    static void idft(std::vector<Mint> &a) {
        atcoder::internal::butterfly_inv(a);
        Mint inv = Mint::raw(a.size()).inv();
        for (Mint &ele : a) {
            ele *= inv;
        }
    }
    static std::vector<Mint> mul(std::vector<Mint> a, std::vector<Mint> b) {
        return atcoder::convolution(a, b);
    }
};

Back to top page