Skip to content

Latest commit

 

History

History

Convolution

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

README.md

クラス Convolution


NTTで剰余Convolutionを計算するクラスです。

使い方

  1. staticな Convolution.convolute を呼び出します.
public static void main(String[] args) {
    // NTT用素数のModを指定します
    int mod = 998244353;
    long[] a = { 1, 2, 3, 4, 5 };
    long[] b = { 6, 7, 8 };
    // 畳み込みを計算しまqす。a.length + b.length - 1 の配列が帰ります。
    long[] ret = Convolution.convolution(a, b, mod);
    System.out.println(Arrays.toString(ret));
}

メソッド

convolution (NTT prime only)

public static long[] convolution(long[] a, long[] b, int mod) 

リストまたは配列 a と b の剰余convolutionを計算します. 計算量: $O(n ¥log(n))$

制約

  • mod NTT用素数(998244353, 1053818881, 1004535809, ...)

convolution (Any mod)

public static long[] convolutionLL(long[] a, long[] b, int mod) 
public static java.util.List<ModIntFactory.ModInt> convolution(
            java.util.List<ModIntFactory.ModInt> a,
            java.util.List<ModIntFactory.ModInt> b
)

リストまたは配列 a と b の剰余convolutionを計算します. 計算量: $O(n ¥log(n))$

制約

  • mod 任意のmod