Dirichlet Convolution
(library/convolution/dirichlet_convolution.hpp)

• View this file on GitHub
• Last update: 2021-08-05 19:28:12+09:00
• Include: #include "library/convolution/dirichlet_convolution.hpp"

dirichlet_convolution

• シグネチャ

  template <typename T>
  std::vector<T> dirichlet_convolution(std::vector<T> a, std::vector<T> b)
  

• 概要

  長さ $N$ の列 $(A_0,A_1,\ldots,A_{N-1})$ および $(B_0,B_1,\ldots,B_{N-1})$ を添字の積で畳み込みます．即ち，長さ $N$ の列 $(C_0,C_1,\ldots,C_{N-1})$ であって，各 $k=0,\ldots,N-1$ に対して以下を満たす列を計算します．

  \[C _ k = \sum _ { i \times j = k } A _ i \cdot B _ j\]

  以下，この畳み込みを $C=A\ast B$ と表記します．

• テンプレート引数

  • T: 列の要素の型．operator+=，operator*= が定義されている必要があります．

• 返り値

  $A\ast B$

• 制約

  • $0 \leq \vert A \vert, \vert B \vert \leq 10 ^ 6$

• 時間計算量

  $\Theta(N\log N)$

dirichlet_convolution_coprime

• シグネチャ

  template <typename T>
  std::vector<T> dirichlet_convolution_coprime(std::vector<T> a, std::vector<T> b)
  

• 概要

  長さ $N$ の列 $(A_0,A_1,\ldots,A_{N-1})$ および $(B_0,B_1,\ldots,B_{N-1})$ を添字の互いに素な積で畳み込みます．即ち，長さ $N$ の列 $(C_0,C_1,\ldots,C_{N-1})$ であって，各 $k=0,\ldots,N-1$ に対して以下を満たす列を計算します．

  \[C _ k = \sum _ { \overset{ \scriptstyle i \times j = k, }{ \gcd (i, j) = 1} } A _ i \cdot B _ j\]

  以下，この畳み込みを $C=A\ast B$ と表記します．

• テンプレート引数

  • T: 列の要素の型．operator+=，operator*= が定義されている必要があります．

• 返り値

  $A\ast B$

• 制約

  • $0 \leq \vert A \vert, \vert B \vert \leq 10 ^ 6$

• 時間計算量

  $\Theta(N\log N)$

Code

#ifndef SUISEN_DIRICHLET_CONVOLUTION
#define SUISEN_DIRICHLET_CONVOLUTION

#include <vector>
#include <limits>

namespace suisen {

template <typename T>
static std::vector<T> dirichlet_convolution(const std::vector<T> &a, const std::vector<T> &b, const int n) {
    std::vector<T> c(n, T(0));
    const int m = std::min(int(a.size()), n), k = std::min(int(b.size()), n);
    for (int i = 1; i < m; ++i) {
        int jmax = std::min((n + i - 1) / i, k);
        for (int j = 1; j < jmax; ++j) {
            c[i * j] += a[i] * b[j];
        }
    }
    return c;
}

template <typename T>
static std::vector<T> dirichlet_convolution_coprime(const std::vector<T> &a, const std::vector<T> &b, const int n) {
    std::vector<T> c(n, T(0));
    const int m = std::min(int(a.size()), n), k = std::min(int(b.size()), n);
    std::vector<std::vector<int>> dp(m);
    for (int i = 1; i < m; ++i) {
        const int jmax = std::min((n + i - 1) / i, k);
        dp[i].reserve(jmax);
        dp[i].push_back(i);
        for (int j = 1; j < jmax; ++j) {
            int g = i > j ? dp[i - j][j] : dp[i][j - i];
            dp[i].push_back(g);
            if (g == 1) c[i * j] += a[i] * b[j];
        }
    }
    return c;
}

} // namespace suisen


#endif // SUISEN_DIRICHLET_CONVOLUTION

#line 1 "library/convolution/dirichlet_convolution.hpp"



#include <vector>
#include <limits>

namespace suisen {

template <typename T>
static std::vector<T> dirichlet_convolution(const std::vector<T> &a, const std::vector<T> &b, const int n) {
    std::vector<T> c(n, T(0));
    const int m = std::min(int(a.size()), n), k = std::min(int(b.size()), n);
    for (int i = 1; i < m; ++i) {
        int jmax = std::min((n + i - 1) / i, k);
        for (int j = 1; j < jmax; ++j) {
            c[i * j] += a[i] * b[j];
        }
    }
    return c;
}

template <typename T>
static std::vector<T> dirichlet_convolution_coprime(const std::vector<T> &a, const std::vector<T> &b, const int n) {
    std::vector<T> c(n, T(0));
    const int m = std::min(int(a.size()), n), k = std::min(int(b.size()), n);
    std::vector<std::vector<int>> dp(m);
    for (int i = 1; i < m; ++i) {
        const int jmax = std::min((n + i - 1) / i, k);
        dp[i].reserve(jmax);
        dp[i].push_back(i);
        for (int j = 1; j < jmax; ++j) {
            int g = i > j ? dp[i - j][j] : dp[i][j - i];
            dp[i].push_back(g);
            if (g == 1) c[i * j] += a[i] * b[j];
        }
    }
    return c;
}

} // namespace suisen

Back to top page