dunkelheit reference

dkh.modint

  • ModInt

    Declaration

    struct ModInt(uint MD) if (MD < (int).max);

    int with mod, mod must be prime

    Examples

    1. alias Mint = ModInt!(107); assert((Mint(100) + Mint(10)).v == 3); assert(( Mint(10) * Mint(12)).v == 13); assert(( Mint(1) / Mint(2)).v == 108/2); assert((Mint(2) ^^ 7).v == 21);

    • opBinary

      Declaration

      const auto opBinary(string op : "+")(ModInt r);
      const auto opBinary(string op : "-")(ModInt r);
      const auto opBinary(string op : "*")(ModInt r);
      const auto opBinary(string op : "/")(ModInt r);
      const auto opBinary(string op : "^^", T)(T r);

      We can handle it as same as int(but divide is slow)

    • inv

      Declaration

      static ModInt inv(ModInt x);

      return 1/x

  • DModInt

    Declaration

    struct DModInt(string name);

    int with mod, mod can be setted in execute time. mod don't have to be prime.

    Examples

    1. alias Mint1 = DModInt!"mod1"; alias Mint2 = DModInt!"mod2"; Mint1.MD = 7; Mint2.MD = 9; assert((Mint1(5)+Mint1(5)).v == 3); // (5+5) % 7 assert((Mint2(5)+Mint2(5)).v == 1); // (5+5) % 9

    • opBinary

      Declaration

      const auto opBinary(string op : "+")(DModInt r);
      const auto opBinary(string op : "-")(DModInt r);
      const auto opBinary(string op : "*")(DModInt r);
      const auto opBinary(string op : "/")(DModInt r);

      整数型と同じように演算可能 割り算のみ遅い

    • inv

      Declaration

      static DModInt inv(DModInt x);

      xの逆元を求める

  • factTable

    Declaration

    T[] factTable(T)(size_t length) if (isModInt!T);

    return [0!, 1!, 2!, ..., (length-1)!]

  • invFactTable

    Declaration

    T[] invFactTable(T)(size_t length) if (isModInt!T);

    return [1/0!, 1/1!, 1/2!, ..., 1/(length-1)!]

  • invTable

    Declaration

    T[] invTable(T)(size_t length) if (isModInt!T);

    return [0, 1/1, 1/2, 1/3, ...]