MOD界の割り算

mod p(p := primary number)での割算 a / b mod pは
a * (b^p-2 % p ) % pで求まる

moddiv.cpp


long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

tmp *= modinv(2, MOD);
tmp %= MOD;

最大公約数

3個の整数の最大公約数は、gcd(gcd(a,b),c)で求まる。同じ要領でn個の最大公約数

gcd.cpp

int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

Vector

(vec.begin())は先頭要素を示すが、(vec.end())は要素ではない。*(--vec.end())とすると末尾要素にアクセスできる
vectorに２つ以上要素をもたせたいときは、pair<> tuple<>が必須

vector.cpp


// 隣接リスト表現
// 頂点n個
vector<vector<pair<ll, ll> > > Graph(n);

// 入れるとき
Graph[x].push_back( make_pair( a,b ) );
Graph[x].push_back( { a,b } ); // -std=c++17の指定が必要

// 取り出すとき
Graph[x][y].first;
Graph[x][y].second;
// or
typedef pair<ll, ll> P;
P p_tmp = Graph[x][y];
p_tmp.first;
p_tmp.second;

#multiset
insertは値を入れる。
eraseは値を入れると同じ値を全部削除してしまうので、かならずms.find(value)でイテレータを渡す。

#小数

誤差について
doubleでは誤差が発生し正しく計算できない場合が多い。対策は下記
- long doubleを使って精度を上げる
- stringで読み込んで小数点を除去して整数に変換する
- 微小値を加算してから整数に変換する
- round関数を使って四捨五入して誤差を飛ばす
出力を Cout にすると、AAAAe+YYYみたいな形式に勝手に変換されてしまうときがある。そのためprintf / もしくは出力形式を指定する必要がある。

decimal.cpp

  cout << fixed << setprecision(15) << y << endl;

#二分探索

lower_bound()/upper_bound()はどちらも指定値以上/より大きい。指定値以下のイテレータを返したかったら、upper_boundして--する。
バグの温床でまともに一発で通すのは難しい。適当に数値を+1とかして帳尻合わせしようとしてもうまく行かない。きっちりかっきり机上デバッグしよう。
もしくはめぐる式
pairのvectorにしなくても、取得したイテレータ - begin()にするとindex求まる(vectorの場合)

lower_bound.cpp

vector<pair<ll, ll > > xxx_total; // pair1つ目には値、pair2つ目にはindex
xxx_total.push_back({xxx_value, xxx_index});
auto xxx_itr = upper_bound(ALL(xxx_total), make_pair(xxx_total,INF)); //　--で後で一個後ろを参照したいので、const auto & itrにはしない
// auto xxx_itr = lower_bound(ALL(xxx_total), make_pair(xxx_total,-INF)); // lowerのときは-INFにしておく必要あり
// auto xxx_itr = lower_bound(ALL(xxx_total), make_pair(xxx_total,0)); // 0の部分で推論ミスってコンパイル通らないのでこれはだめ

// 指定値より大きい値のイテレータが帰ってきてるわけだから、うまく帳尻合わせする。
if(xxx_itr == end(xxx_total)){
    ans_index = xxx_total.size();
}else if(xxx_itr == begin(xxx_total)){
    ans_index = 0;
}else{
    ans_index = (*(--b_itr)).second;
    //ans_index = ll(b_itr - begin(xxx_total)); じつはこれでも
}

#その他

__builtin_popcount(input) inputのonbit数を求める(templete)

#問題への取り組み方
###数学系問題

ノートを使用する
全探索で解けるか
妙に厳しい制約がないか。これを活かせないか
小さい数値/正の整数で試行する。周期性や単調増加/減少といった特徴が見つからないか
文章から数式を立式できないか。数式を変換できないか。式を変形して小数や√を消滅させることができないか(誤差に注意)
沢山の変数がうじゃうじゃ動くときは、一文字だけ動かしてみる。実は特定の範囲の値が自在に作れるかも
二次元グルーピングで考えることができないか（ABC172D, ARC117B)
DPは遷移式まで描いてから考えないと、必ずバグるので注意。特に、もらうか配るか常に考える。

###留意すべき観点

全探索するときの、forループの回し方に注意する。forループの回し方を変化させることで高速化できるかも
結構forの回し方を考えずに実装してTLEする～に陥ってるため気をつける。
入力で渡される値ではなく、出力する答えをiにして、iのときに答えの条件を満たしているかを確認する(ABC172C)
[1...n]を出力に要求されているとき、仕分けして最後に一気に出力すると早い場合がある(aising2020C)

参考元

mod界の除算
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#4-%E7%B4%AF%E4%B9%97-an
最大公約数
https://note.com/kazusasan/n/n9ea759286ea3
小数
https://cpprefjp.github.io/reference/ios/defaultfloat.html
https://drken1215.hatenablog.com/entry/2020/05/31/224300
問題への取り組み方
https://speakerdeck.com/furuya1223/the-view-of-green-difficulty-problems
https://algo-logic.info/how-to-think-cp/