競技プログラミングでよく使う便利系関数をまとめてみた

　今回はAtCoderでよく使う便利系関数をまとめてみました。とりあいず今思いつく範囲で書いてますが、思い出したら追加していきます。

0.前提

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=pow(10,9)+7;

　前提として以上のようにしています。

1.最大公約数、最小公倍数

ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

　gcdが最大公約数、lcmが最小公倍数です。どちらも計算量はO(log N)程度らしいです。lcmはa/gcd(a,b)*bとしてるのがポイントです。(オーバーフローしないように)

2.modPow

ll modPow(ll x,ll n,ll mod=MOD){
    if(n==0)return 1;
    if(n%2==0)return modPow(x*x,n/2,mod)%mod;
    return x%mod*modPow(x,n-1,mod)%mod;
}

　xのn乗をmodで割ったものを返します。繰り返し2乗法を用いてるため計算量はO(log N)と高速です。

3.各位の和を返す

ll getSumDigit(ll N){
    string s=to_string(N);
    ll ret=0;
    for(int i=0;i<s.size();i++)ret+=(s[i]-'0');
    return ret;
}

4.nCk mod p

class Combination{
public:
    vector<ll>fac;
    vector<ll>finv;
    vector<ll>inv;

    Combination(ll MAX,ll mod=MOD){
        fac.resize(MAX+2);
        finv.resize(MAX+2);
        inv.resize(MAX+2);
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < MAX; i++){
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
    }

    ll com(int n, int k){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
};

コンビネーションをmodで割った余剰を求めるものを求めるものです。この記事を参考(丸パクリ)してます。本家ではグローバル変数でやってましたが、クラス化してます。前処理でO(N)、comはO(1)で返すことができます。

5.ランレングス圧縮っぽいもの

vector<ll> countVector(vector<ll>v,ll guard=-1){
    ll size=v.size();
    //番兵を追加(初期値は-1)
    v.push_back(guard);
    vector<ll>ret;
    ll count=1;
    for(int i=0;i<size;i++){
        if(v[i]==v[i+1]){
            count++;
        }else{
            ret.push_back(count);
            count=1;
        }
    }
    return ret;
}

(2019/12/24追記)うまく言えませんが、例えば{2,2,2,3,3,1,2}を渡したら{3,2,1,1}みたいに連続する個数の配列を返す関数です。意外とよく使うので便利です。
(2019/12/29追記)ランレングス圧縮なんていうそうです。

INF.最後に

　一旦はこんな感じでまとめてみました。思い出したら追加していきます。お役になてれば幸いです。最後になりましたが、コードを勝手に参考にさせていただいた方ありがとうございましたm(_ _)m