acl_cpp.convolution

from acl_cpp.convolution import convolution998244353, convolution, convolution_ll

convolution.convolution998244353

# vector<modint998244353> convolution<998244353>(vector<modint998244353> a, vector<modint998244353> b)
def convolution998244353(a: list[int], b: list[int]) -> list[int]

If at least one of \(a\) or \(b\) is an empty array, returns an empty array. Otherwise, returns an array \(c\) of length \(\text{len}(a) + \text{len}(b) - 1\) defined as follows.

\[c[k] = \left(\sum_{i + j = k} a[i] \cdot b[j]\right) \bmod {998244353}\]

Constraints

\(0 \leq a[i], b[i] < 998244353\)
\(\text{len}(a) + \text{len}(b) - 1 \le 2^{23}\)

Behavior is undefined if \(0 \leq a[i], b[i] < 998244353\) is not satisfied.

Complexity

Let \(n = \text{len}(a) + \text{len}(b)\), then

\(O(n \log n)\)

convolution.convolution

# dynamic_modint version of convolution
def convolution(a: list[int], b: list[int], p: int) -> list[int]

If at least one of \(a\) or \(b\) is an empty array, returns an empty array. Otherwise, returns an array \(c\) of length \(\text{len}(a) + \text{len}(b) - 1\) defined as follows.

\[c[k] = \left(\sum_{i + j = k} a[i] \cdot b[j]\right) \bmod {p}\]

Constraints

\(0 \leq a[i], b[i] < p\)
\(2 \le p \lt 2^{31}\)
\(p\) is a prime number
There exists a non-negative integer \(k\) such that \(\text{len}(a) + \text{len}(b) - 1 \le 2^k\) and \(p-1\) is a multiple of \(2^k\)

Behavior is undefined if \(0 \leq a[i], b[i] < p\) is not satisfied.

Complexity

Let \(n = \text{len}(a) + \text{len}(b)\), then

\(O(n \log n + \log p)\)

convolution.convolution_ll

# vector<ll> convolution_ll(vector<ll> a, vector<ll> b)
def convolution_ll(a: list[int], b: list[int]) -> list[int]

Calculates the convolution. If at least one of \(a\) or \(b\) is an empty array, returns an empty array.

Constraints

\(\text{len}(a) + \text{len}(b) - 1 \le 2^{24}\)
\(-2^{63} \le a[i], b[i] < 2^{63}\)
The resulting array \(c\) satisfies \(-2^{63} \le c[i] < 2^{63}\)

Behavior is undefined if \(-2^{63} \le c[i] < 2^{63}\) is not satisfied.

Complexity

Let \(n = \text{len}(a) + \text{len}(b)\), then

\(O(n \log n)\)

internal.convolution

Source code

from acl_cpp.internal.convolution import butterfly998244353, butterfly, butterfly_inv998244353, butterfly_inv

Since lists cannot be modified by reference, the modified list is returned.
The butterfly function is useful for speeding up convolutions and FPS (Formal Power Series).
butterfly_inv(butterfly(a)) multiplies each element by len(a), so you need to divide by len(a).

internal.convolution.butterfly998244353

# void butterfly<modint998244353>(vector<modint998244353> &a)
def butterfly998244353(a: list[int]) -> list[int]

Let \(\text{len}(a) = 2^k\) and define the function \(\text{bit_reverse}(x)\) as the integer obtained by reversing the lower \(k\) bits of \(x\). Using the primitive \(2^k\)-th root of unity \(g\) modulo \(998244353\), returns an array \(b\) of length \(2^k\) defined as follows.

\[b[\text{bit_reverse}(i)] = \left(\sum_{j = 0}^{2^k-1}g^{ij} \cdot a[j]\right)\bmod{998244353}\]

Constraints

There exists an integer \(0 \le k \le 23\) such that \(\text{len}(a) = 2^k\)
\(0 \leq a[i] < 998244353\)

Behavior is undefined if \(0 \leq a[i] < 998244353\) is not satisfied.

internal.convolution.butterfly998244353_inv

# void butterfly<modint998244353>(vector<modint998244353> &a)
def butterfly998244353_inv(a: list[int]) -> list[int]

Let \(\text{len}(a) = 2^k\) and define the function \(\text{bit_reverse}(x)\) as the integer obtained by reversing the lower \(k\) bits of \(x\). Using the primitive \(2^k\)-th root of unity \(g\) modulo \(998244353\), returns an array \(b\) of length \(2^k\) defined as follows.

\[b[i] = \left(\sum_{j = 0}^{2^k-1}g^{-ij} \cdot a[\text{bit_reverse}(j)]\right) \bmod {998244353}\]

Constraints

There exists an integer \(0 \le k \le 23\) such that \(\text{len}(a) = 2^k\)
\(0 \leq a[i] < 998244353\)

Behavior is undefined if \(0 \leq a[i] < 998244353\) is not satisfied.

internal.convolution.butterfly

# dynamic_modint version of butterfly
def butterfly(a: list[int], p: int) -> list[int]

Let \(\text{len}(a) = 2^k\) and define the function \(\text{bit_reverse}(x)\) as the integer obtained by reversing the lower \(k\) bits of \(x\). Using the primitive \(2^k\)-th root of unity \(g\) modulo \(p\), returns an array \(b\) of length \(2^k\) defined as follows.

\[b[\text{bit_reverse}(i)] = \left(\sum_{j = 0}^{2^k-1}g^{ij} \cdot a[j]\right)\bmod{p}\]

Constraints

There exists a non-negative integer \(k\) such that \(\text{len}(a) = 2^k\) and \(p-1\) is a multiple of \(2^k\)
\(2 \le p \lt 2^{31}\)
\(p\) is a prime number
\(0 \leq a[i] < p\)

Behavior is undefined if \(0 \leq a[i] < p\) is not satisfied.

internal.convolution.butterfly_inv

# dynamic_modint version of butterfly_inv
def butterfly_inv(a: list[int], p: int) -> list[int]

Let \(\text{len}(a) = 2^k\) and define the function \(\text{bit_reverse}(x)\) as the integer obtained by reversing the lower \(k\) bits of \(x\). Using the primitive \(2^k\)-th root of unity \(g\) modulo \(p\), returns an array \(b\) of length \(2^k\) defined as follows.

\[b[i] = \left(\sum_{j = 0}^{2^k-1}g^{-ij} \cdot a[\text{bit_reverse}(j)]\right) \bmod {p}\]

Constraints

There exists a non-negative integer \(k\) such that \(\text{len}(a) = 2^k\) and \(p-1\) is a multiple of \(2^k\)
\(2 \le p \lt 2^{31}\)
\(p\) is a prime number
\(0 \leq a[i] < p\)

Behavior is undefined if \(0 \leq a[i] < p\) is not satisfied.

Examples

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_f

from acl_cpp.convolution import convolution998244353

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = convolution998244353(A, B)

print(*C)

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_f

from acl_cpp.convolution import convolution

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = convolution(A, B, 998244353)

print(*C)