NyaanNyaan
NyaanNyaan
問題名: Division of Polynomials # 問題概要 多項式f(x) = sum_{i=0..N-1} f_i x^i, g(x) = sum_{i=0..M-1} g_i x^i が与えられます。 次の条件を満たす多項式q(x),r(x)を求めてください。 - f(x) = q(x)g(x) + r(x) - deg(r) < deg(g) ## 制約...
問題名: Ordered Associative Array 想定アルゴリズム: 平衡二分木, 動的セグ木(必要なところだけ作るセグ木) ## 問題概要 空の連想配列aが与えられます。以下で説明されるクエリを順にQ回処理してください。 0 k v : キーと値の組(k, v)をaに追加する。ただしキーがkである組が存在するときは、既存の組の値をvに書き換える。 1 k : キーがkである組をaから削除する。ただしキーがkである組が存在しないときは何もしない。 2 k : a[k]を出力する。(存在しない場合は-1を出力する。) 3 k : キーの値がk以下である組の個数を出力する。 4 i...
## Description / 説明 インタラクティブ問題でのデバッグを速やかに行うために、 oj test-reactive に複数のテストケースを実行するオプションがあると大変ありがたいです。 ## Motivation / 動機 コンテスト中に自分のプログラムのバグを特定したいとき、インタラクティブでない場合は oj generate-input を利用することで WA を返すケースを発見することができます。このとき適切なオプションをつけることで hack できるまで連続実行することが可能になり、テストケースを1秒に数十ケース単位で実行することができて非常に便利です。 一方、インタラクティブでも oj test-reactive を利用すれば可能ですが、連続実行を行うオプションがありません。シェルの機能を利用すればループさせることは可能ですが、毎回 oj を起動して終了させるのが重いのか（ここきちんと検証していません、すみません) 小さいケースでも手元で一回あたり 0.5 秒程度かかってしまいます。 oj...
## 書くべきこと(仮) - 概要 (1~2 行でよい) - テンプレート引数の説明 - 関数の説明・計算量 - 使用上の注意 #### 必要かどうか微妙なラインのもの - メンバ変数の説明 (内部の変数を触ることを想定したライブラリっぽそうなら必要) 他に何かあったら教えてください ## ドキュメントに要らない部分をどうするか - 関数の使い方を書かずにアルゴリズムの詳細な説明だけ書いていることがある - リファレンスとして役に立たず、邪魔なだけ - なんらかの対策を取るべきか？ - 別サイトを作ってそちらにアルゴリズムの話を移す - そのまま残して、下部に関数の説明などを書く...
現状のfastioはchar,Integralしか吸えない。stringも吸えるようにするべき
かなり中途半端なので改良するか消すかするべき
https://github.com/NyaanNyaan/library/blob/76ea294182f34ee64f792ce6aeb849fa19f8e6ef/modint/barrett-reduction.hpp#L31 modが1の時にバグる https://github.com/NyaanNyaan/library/blob/76ea294182f34ee64f792ce6aeb849fa19f8e6ef/modint/arbitrary-modint.hpp#L6 modが2e9の時にバグる すべてのmodintに対してテストを書く
バグを直したらだいぶ遅くなったような気がする 暇なときに原因を調べる, 場合によっては erase 不可能な hashmap を作る