パッケージ library

クラス ModuloCalculation

  • class ModuloCalculation
extends java.lang.Object
    モジュロ演算のライブラリ

    • ネストされたクラスの概要

      ネストされたクラス 
      修飾子とタイプ クラス 説明
      private static class  ModuloCalculation.CombinationCalculator
      高速にmod込みで組み合わせを計算できる．

    • コンストラクタの概要

      コンストラクタ 
      コンストラクタ 説明
      ModuloCalculation()  

    • メソッドの概要

      すべてのメソッド staticメソッド concreteメソッド 
      修飾子とタイプ メソッド 説明
      private static long[][] createCombinationTable​(int size)
      組み合わせの計算をDPを用いて高速化する．
      private static long modInv​(long a, long mod)
      素数modを法としたaの逆元を計算する．

      • クラスから継承されたメソッド java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • コンストラクタの詳細

      • ModuloCalculation

        ModuloCalculation()

    • メソッドの詳細

      • createCombinationTable

        private static long[][] createCombinationTable​(int size)
        組み合わせの計算をDPを用いて高速化する．

        ModuloCalculation.CombinationCalculator の方が計算量，メモリ容量的に使いやすい．

        パラメータ:
        size - 二次元配列のサイズ 　配列の大きさから size C x はできないことに注意
        戻り値:
        二次元配列

      • modInv

        private static long modInv​(long a,
                           long mod)
        素数modを法としたaの逆元を計算する．

        BigInteger.valueOf(a).modInverse(mod).longValue() でも同じことができそう

        パラメータ:
        a - 逆元を計算したい値
        mod - 法となる素数
        戻り値:
        modを法としたaの逆元