modint_chaemonの修正

[haruyama480]

close: https://github.com/zer0-star/Nim-ACL/issues/59

対応内容

• apple siliconでも動くように、import std/distrosして条件分岐を追加
• マクロも壊れていそうだったので動くように修正

提出後しても動くことを確認 https://atcoder.jp/contests/typical90/submissions/46886132

[chaemon]

それ、自分で実装しておいてなんですが、忘れちゃいましたね。atcoder/modintが出る前から使ってて、atcoder/modintが出てからは使わなくなってしまいました。

atcoder/modintと比べた違いはアセンブリによる処理が入っているところですかね。そうだとしたら、名前があれなので、modint_asmとかにしましょうか。アセンブリにすることで早くなるんですかね。

他に、Nyaanさんの実装を参考にしたモントゴメリー演算によるmodintもあります。atcoder/extra/math/modint_montgomeryだったと思います。

[haruyama480]

そうだったんですね！

自分は

declareDMint(mint13); mint13.setMod(13)
declareDMint(mintN); mintN.setMod(N)

みたいに1行で、動的な値を法としたmintを2つ以上定義できるので使おうとしていました

[haruyama480]

どちらかといえばmodint_chaemonを消して、モンゴメリの方にdeclareDMintを定義するのがいいですかね？

[chaemon]

そうだったんですね！

自分は

declareDMint(mint13); mint13.setMod(13)
declareDMint(mintN); mintN.setMod(N)

みたいに1行で、動的な値を法としたmintを2つ以上定義できるので使おうとしていました

それは本家のatcoder/modintの方でもできるのではないですかね？作った気がします。アセンブリとかモンゴメリとかは早い（？）分なんか不具合がありそうなので、基本は本家推奨でその他は定数倍で早くしたい人向けにしたいですかね〜

[haruyama480]

~atcoder/modint のdynamicなものは複数定義できないみたいです~

import atcoder/modint

useDynamicModInt(mint, 998244353)
useDynamicModInt(boolean, 2)

echo boolean(1) # 1
echo boolean(-1) # 998244352. 本当は1が欲しい

~そっちを修正したほうが良さそう~

[haruyama480]

嘘です

useDynamicModInt(mint, -1); mint.setMod 998244353
useDynamicModInt(boolean, -1); boolean.setMod 2

で動きました

[haruyama480]

うーん、でも、modint_asmが通ったサンプルテスト通らないなあ

# #contest_doc
# name Flip_Flap（★6）
# url https://atcoder.jp/contests/typical90/tasks/typical90_be
# version 0.0.1

{. warning[UnusedImport]:off .}
import sequtils, math, algorithm, strutils, strformat, bitops, deques, heapqueue, hashes, sets, tables, lists, sugar
import harulib/utils
import atcoder/extra/other/sliceutils
import atcoder/extra/math/matrix

# import atcoder/extra/math/modint_asm
# declareDMint(mint); mint.setMod 998244353
# declareDMint(boolean); boolean.setMod 2

import atcoder/modint
useDynamicModInt(mint, -1); mint.setMod 998244353
useDynamicModInt(boolean, -1); boolean.setMod 2

input:
  (N,M):int

A := makeSeq([N, M], 0)
for i in N:
  input:
    T: int
    a: seq[int1]
  for t in T:
    A[i][a[t]] = 1
input:
  S: seq[int]

let
  d1 = DynamicMatrixType(boolean).init(A&S).gaussianElimination[1].len
  d2 = DynamicMatrixType(boolean).init(A).gaussianElimination[1].len

if d1 == d2:
  echo mint(2)^(N-d2)
else:
  echo 0

=================== test start ===================
test/typical90_be.cases/0.in
runtime: 1.24[s]
test/typical90_be.cases/1.in
runtime: 0.09[s]
test/typical90_be.cases/2.in
runtime: 0.08[s]
1c1
< 0
---
> 2
test/typical90_be.cases/3.in
runtime: 0.09[s]
1c1
< 0
---
> 128
test/typical90_be.cases/4.in
runtime: 0.09[s]
test/typical90_be.cases/5.in
runtime: 0.08[s]
==================== test end ====================

[chaemon]

行列を使ってるようなんですが、その行列の実装がまた癖のあるもので、そのへんが怪しいです。 よく使いこなしてるなぁという印象ですね！

[chaemon]

useDynamicModIntの第２引数はIDみたいなものなので、別々に使うなら両方-1ではいけない気がします。両方-1にするとbooleanもmintも両方mod 2になります

[haruyama480]

(Z/nZでもガウスの消去法効くの嬉しすぎますね)

ありがとうございます! -2にしたらすんなり通りました!! 行列の方は問題なさそうです

[haruyama480]

atcoder/modintを基本的に使うのが良さそうですね

使ってなさそうならmodint_asmは消しちゃいますか？

[chaemon]

atcoder/modintに比べて早くなるんでしたっけ？

早くなるなら定数倍高速化したい人向けに残しておきたいですね。

あと、通常のac-libraryのもの、アセンブリのもの、モンゴメリー演算のものを一箇所書き換えるだけで切り替えられるようにしておきたいです。

[haruyama480]

ですねえ、 ぱっと直らない&試せなかった(asmはintelのみ)ので一旦マージとしておきますm(__)m

[chaemon]

うーん、でも、modint_asmが通ったサンプルテスト通らないなあ

# #contest_doc
# name Flip_Flap（★6）
# url https://atcoder.jp/contests/typical90/tasks/typical90_be
# version 0.0.1

{. warning[UnusedImport]:off .}
import sequtils, math, algorithm, strutils, strformat, bitops, deques, heapqueue, hashes, sets, tables, lists, sugar
import harulib/utils
import atcoder/extra/other/sliceutils
import atcoder/extra/math/matrix

# import atcoder/extra/math/modint_asm
# declareDMint(mint); mint.setMod 998244353
# declareDMint(boolean); boolean.setMod 2

import atcoder/modint
useDynamicModInt(mint, -1); mint.setMod 998244353
useDynamicModInt(boolean, -1); boolean.setMod 2

input:
  (N,M):int

A := makeSeq([N, M], 0)
for i in N:
  input:
    T: int
    a: seq[int1]
  for t in T:
    A[i][a[t]] = 1
input:
  S: seq[int]

let
  d1 = DynamicMatrixType(boolean).init(A&S).gaussianElimination[1].len
  d2 = DynamicMatrixType(boolean).init(A).gaussianElimination[1].len

if d1 == d2:
  echo mint(2)^(N-d2)
else:
  echo 0

=================== test start ===================
test/typical90_be.cases/0.in
runtime: 1.24[s]
test/typical90_be.cases/1.in
runtime: 0.09[s]
test/typical90_be.cases/2.in
runtime: 0.08[s]
1c1
< 0
---
> 2
test/typical90_be.cases/3.in
runtime: 0.09[s]
1c1
< 0
---
> 128
test/typical90_be.cases/4.in
runtime: 0.09[s]
test/typical90_be.cases/5.in
runtime: 0.08[s]
==================== test end ====================

そういえばこちらについて、DynamicModIntの用途はmodが入力で与えられたり、途中で変わったりする場合なので、2や998244353のようにコンパイル時にわかっていて変更しないならStaticModIntが使えて、そっちのほうが早いですよ〜

[haruyama480]

2つ以上定義するケースをテストしたかったため、staticで済むケースを流用していましたmm

[chaemon]

または、d1, d2を計算した後にsetMod 998244353をすればDynamicModInt一個だけで済みますね〜DynamicModIntの数を節約する理由はあまりないですが。。。