habara-k / ICPCLibrary

https://habara-k.github.io/ICPCLibrary/

3 stars 0 forks source link

FPSの実装 #62

Closed habara-k closed 3 years ago

habara-k commented 3 years ago

cf. https://github.com/habara-k/ICPCLibrary/issues/32

DONE

Math

[x] Inv of Formal Power Series https://judge.yosupo.jp/submission/27774
[x] Exp of Formal Power Series https://judge.yosupo.jp/submission/27775
[x] Log of Formal Power Series https://judge.yosupo.jp/submission/27776
[x] Pow of Formal Power Series https://judge.yosupo.jp/submission/27777

modintのリファクタ

内部で値をintで持つようにした
逆元を求めるのにpow(mod-2)をする代わりに~いい感じのコード~ 非再帰の拡張GCD？で計算するようにした

kanra824 commented 3 years ago

NTTもそうなんだけど、FPS<>と書かなくていいように構造体の内部に定数を持たせるのはどうでしょう

habara-k commented 3 years ago

NTTもそうなんだけど、FPS<>と書かなくていいように構造体の内部に定数を持たせるのはどうでしょう

とりあえず先に言い訳を並べます

c++17以降なら FPSとだけ書いても怒られない
定数をメンバに持つ場合、FPSのコピーコストが上がる
定数をstaticに持つ場合、外部からmodを設定できない（FPSの中身のソースコードを直接いじればいいけど、例えば違うmodのFPSをテストしたいときCIどう回すの問題が...）
違うmodが共存できなくなる（必要かどうかは諸説）
modを含めて1つの型になるのが綺麗（宗教）

結論あんまりその変更は乗り気じゃないです

kanra824 commented 3 years ago

怒られないマジ？

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  vector<NTT::Int> a = {1, 2, 3};
  vector<NTT::Int> b = {2, 3, 4};
  NTT ntt;
  cout << ntt.multiply(a, b) << endl;

  return 0;
}

これそっちの環境だと通りますか？

kanra824 commented 3 years ago

FPSは怒られないかも

habara-k commented 3 years ago

ア NTTは無理この辺よくわからないんですよね

kanra824 commented 3 years ago

型テンプレートの中でみたいにすると怒られるなわからねー

kanra824 commented 3 years ago

や、まあ面倒なだけなので、理由があるなら全然いいと思います

habara-k commented 3 years ago

タイプ数減らすためにconst消すか

kanra824 commented 3 years ago

ヨシ！

habara-k commented 3 years ago

タイプ数減らすためにconst消すか

そんなに減らんかったのでこれなしで