habara-k / ICPCLibrary

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

3 stars 0 forks source link

SpeedUp FPS #65

Closed habara-k closed 3 years ago

habara-k commented 3 years ago

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

DONE

KUPCのMが通った https://atcoder.jp/contests/kupc2020/submissions/17606458

yosupo judgeも4倍くらい速くなった

Before https://judge.yosupo.jp/submission/27777
After https://judge.yosupo.jp/submission/27861

実装は何も理解してない

仕様変更

modint

inv, -, pow にconst をつけた
invを拡張GCDではなくpow(mod-2)に戻した
コンストラクタの引数をlong longに戻した（long longの値で初期化したいことが普通にあることに気がついた）cinでの入力時も同様

NTT

今まではオブジェクトを生成してから使っていたが、staticでも行えるようになった。

Before

vector<NTT<>::Int> a, b;
NTT<> ntt;
auto c = ntt.multiply(a, b);

After

vector<NTT<>::Int> a, b;
NTT<> ntt;
auto c = ntt.multiply(a, b);
auto c = NTT<>::multiply(a, b);  // こっちもOK！

kanra824 commented 3 years ago

sugoi

kanra824 commented 3 years ago

よいとおもいます