【競プロライブラリ】mint(modint)で学ぶC++

はじめに

競技プログラミングでよく問題で使われる

答えがとても大きくなる可能性があるので、その量を 1000000007 で割ったあまりを求めよ。

そういった問題に対して、「1000000007 で割ったあまり」を意識しないで使うことのできるmintクラス(構造体)というものが存在します。
AtCoderの解説放送でも登場してきていますね。AtCoder解説放送ライブラリ集

実際のところ、C++を競技プログラミングでしか使っていない人には理解するのが難しいんじゃないかと思います。
ということで、mint を理解しながら C++ も理解しようというのが今回の流れです。

私もC++歴は1年くらいしかないので間違っていたら教えて下さい。
(「独習C++」と「Effective C++」で学んだことを基にしてます)

mint

解説放送で使われている構造体をクラスにして、少し加えたもので説明します。
今回使用するコードはこちらです。

const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

これを基に説明していきたいと思います。
その前に構造体とクラスどっち使えばいいのかわからない人に説明します。

構造体(struct)とクラス(class)の違い

C言語では構造体がありましたが、関数を中に定義することが出来なかったです。(厳密には、関数ポインタを使えば一応できます)
しかしC++では構造体でも関数を定義できるようになったので、構造体とクラスの内容はほぼ一緒です！！！

何が違うかというと

• 構造体はデフォルトのアクセシビリティが public
• クラスはデフォルトのアクセシビリティが private

struct Hoge{
    int value;   // デフォルトのアクセシビリティは public
};

class Fuga{
    int value;   // デフォルトのアクセシビリティは private
};

int main(){
   Hoge x;
   Fuga y;
   x.value = 5;   // public ならアクセスできる
// y.value = 10;  // これはprivateなので外部であるメイン関数からはアクセスできない(Error)
}

privateなメンバ変数や関数はそのクラス(構造体)内でしか使えません。
public: と記載することでそれより下のメンバはpublicになります。

業務ではカプセル化(外部から直に参照や操作をする必要のない内部の状態や構造は隠す)しなければならないのでクラスが用いられます。

競プロでは隠す必要がないので構造体を使う人が多い気がします。

結局ほとんど一緒なのでお好きなほうを使いましょう。
私の好みで今回はクラスでやります。

コンストラクタ

それでは関数一つずつ説明していきます。
まずはコンストラクタ！
コンストラクタとはメイン関数などで宣言(インスタンス生成)をしたときに呼ばれるものです。
基本的にコンストラクタでは初期化を行います。

ちなみに、コンストラクタを定義しないとデフォルトコンストラクタをコンパイラが自動生成してくれます。

mint(long long x=0) : x((x%mod+mod)%mod) {}

mintでは、上の部分です。
コンストラクタの宣言はクラス名と同じ名前を宣言します。
: x((x%mod+mod)%mod)　
ここ意味わからないですよね？？
これは初期化子リストといって下のコードと最終的な結果は一緒です。

mint(long long x=0){
    x = (x % mod + mod) % mod;
}

コードの中身は x % mod したもので初期化しています。
後ろのmodを足して余りを出している部分は、マイナスの値が入ったときも正しい値が出るようにしています。(余りは必ず正の値になる)

初期化子リスト

初期化子リストの使用例を示します。

#include <bits/stdc++.h>
using namespace std;
class Hoge {
public:       //今回ここはpublicにしてます
   int x;
   vector<int> y, z;
   Hoge() : x(5), 
            y(3),        //vectorの普通のコンストラクタ
            z() {}       //vectorのデフォルトコンストラクタ
   Hoge(int x, vector<int>& y, int n) : 
            x(x),   
            y(y),        //vectorのコピーコンストラクタ
            z(n, -1) {}  //vectorの普通のコンストラクタ
};
int main() {

    Hoge a;
    cout << a.x << " " << a.y.size() << " " << a.z.size() << endl;
    // 出力は 5 3 0
    // a.y の要素は {0, 0, 0}
    // a.z の要素は {} 空配列
    vector<int> v = {1, 2, 3, 4, 5};
    Hoge b(10, v, 2);
    cout << b.x << " " << b.y.size() << " " << b.z.size()<< endl;
    // 出力は 10 5 2
    // b.y の要素は {1, 2, 3, 4, 5}
    // b.z の要素は {-1, -1}
    return 0;
}

コンストラクタは複数宣言することが出来ます。
メイン関数の Hoge a は上のコンストラクタが呼ばれ、Hoge b では下のコンストラクタが呼ばれています。
vectorなどのコンテナクラスの初期化は b.y のように直接コピーするような形(コピーコンストラクタ)と a.z や b.z のように配列の個数を宣言する形(普通のコンストラクタ)で初期化できます。

初期化子リストのメリット

class Person {
    string name;
    string address;
    int age;
public:
    Person(string name, string address, int age)  {
        name = name; 
        address = address;
        age = age;
    }
};

Person のコンストラクタ本体が実行される前に、それぞれのデフォルトコンストラクタ(引数を取らないコンストラクタ)が行われて、その直後に代入をするという2回の命令で実行されています。

class Person {
    string name;
    string address;
    int age;
public:
    Person(string& name, string& address, int age) 
        : name(name), address(address), age(age) {}
};

一方こちらはコピーコンストラクタと呼ばれるもの1度だけで初期化されます。

初期化子リストを使ったほうが命令が少ないので、ほとんどの場合で効率的になります。

今回の mint のメンバである x はlong long 型です。これは組み込み型(intやdoubleなど)なのでコンストラクタが呼ばれることはありません。
つまり、初期化子リスト方法と代入の方法で効率に違いはありません。

しかし、コードに一貫性を持たせるためにも初期化子リストを使うのが良いでしょう。

参照(&)

これまでに出てきた関数の引数に参照(&)がついていたものが何回か出てきました。

参照について分からない人は、こちらの記事を見て下さい。
「値渡し」と「参照渡し」の話

クラスを引数で渡す場合、私は値渡しではなくconst参照渡しにします。
極端な例ですが以下のような関数を作ったとします。

void f(vector<vector<set<string>>>> v) {
   // なんかの処理
}

値渡しをするとコピーが渡されるのでコピーコンストラクタが呼ばれます。
すると、上の例ではstring, set, vector, vectorの4つのコピーコンストラクタが呼び出されます。
また、関数が終了する時には仮引数は破棄されるので、デストラクタも4回呼ばれます。
計8回の無駄な処理が生まれてしまい効率が落ちます。
これは参照をつけることで解決できます。

void f(const vector<vector<set<string>>>>& v) {
   // なんかの処理
}

const は不用意な値を変更を防ぐことができます。
constと参照渡しを組み合わせるconst参照渡しは値渡しと同じ働きをすることができます！

const

「Effective C++」という本では、

可能ならいつでもconstをつけよう

という項目があります。

constをつけると変更してはいけないという意味的な制約をはっきりさせ、コンパイラがその制約を守ってくれます。

constをつけることで、関数を使う人の誤用する可能性や間違えて値を書き換えてしまうなどのミスする可能性を低くできます。

constなメンバ関数

constなメンバ関数とは mint の operator+ などの後ろに const がついているもののことです。

               // この後ろのconstのこと↓
mint operator+(const mint& a) const {
    mint res(*this);
    return res+=a;
}

関数の後ろについている const は、クラスのメンバ(mintではxのこと)を変更しないという意味です。

そのような関数が重要である理由は、クラスのインターフェースを理解しやすくするという点です。
これはどのメンバ関数がオブジェクトを変更し、どのメンバ関数が変更しないか、という区別が容易にできるからです。

ライブラリとかは積極的にconstつけましょう！！！

競プロのコンテスト中はconstつける時間は無駄なので付けなくていいです。
(const付けてたら解くの遅くなったと言われても困ります)

オペレータ演算子

mint の大部分であるオペレータ演算子のオーバーロードについてです。
演算子のオーバーロードは、独自のクラスに対する拡張です。
operatorというキーワードとシンボルを組み合わせて宣言します。

オーバーロードされた演算子が行う処理の内容や戻り値の型に何の制約も設けていませんが、一般的には、オーバーロードされた演算子は組み込みの演算子と可能な限り似たように振る舞うように作るべきです。

単項演算子

符号やインクリメントなどを表すものなどです。
-演算子との区別は引数によってしています。

mint operator-() const { 
    return mint(-x);
}

mintでは上記のコードです。
これは - で初期化したものを返しています。

複合代入演算子

    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }

基本的に % 演算は処理速度が +, - などに比べて特に遅いです。

x は mod で余りを取り続けているので 2 * mod より大きくならないことを利用して、+と―だけを用いて高速化を実現しています。
operator/= の 処理が分からない方は、この後のinv関数のところリンク(けんちょんさんの記事)をみて下さい。

複合代入演算子のオーバーロードは、代入演算子と同じ形になります。
すなわち、自身と同じ型の参照を引数にとり、戻り値は *this を参照で返します。
また、メンバ変数の書き換えが起こるので、constメンバ関数にはなりません。

代入演算子(コピー代入演算子)

コピー代入演算子はつなげて使うことができるのが、１つの特徴です。

int a, b, c;
a = b = c = 15;
// a = (b = (c = 15))と解釈される

コピー代入演算子は右結合であることも特徴になっています。
これは、コピー代入演算子が**「左辺への参照」を戻す**ことで実現されています。
なので、operator=のオーバーロードでは *this が使われます。

算術演算子

    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

引数に右オペランドをもらいます。
今回の *this は左オペランドを表し、それをコピーコンストラクターで受け取り複合代入演算子をします。
(コピーコンストラクタを定義していないですが、コンパイラが自動生成してくれます)

sum = a + b;
// aが左オペランド　bが右オペランド
// sum = a.operator(b) が呼ばれる。

見てわかるように算術演算は複合代入演算子を用いているのでsum = sum + aより、sum += aの方が効率面で優れています。

その他メンバ関数

pow関数とinv関数がありますが、けんちょんさんの記事を参考にしたほうが良いと思いますのでそちらを見てください。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜

• pow関数

  累乗 a^n (二分累乗法)

• inv関数

modでの割り算(逆元)

出力

解説放送のライブラリでの出力は cout << ans.x << endl;としないといけないですが、
それをcout << ans << endl;で出来るようにします。

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }

クラス型の変数をストリーム挿入演算子 (<<) に直接指定できるようにするには、そのクラス内ではなくて外側に "operator<<" のオーバーライドを定義します。

ストリーム挿入演算子の実装は、クラスの実装とは違うところでやっているので、そのままだとクラス内の private メンバにアクセスすることができません。

クラスの値をデータ出力する上で private メンバにアクセスする必要がある場合には、クラスの定義の中で、このストリーム挿入演算子を friend 指定しておくようにします。

そうすることで private メンバでもアクセスできるようになるので出力の簡易化が実現できます。

例をあげると以下のコードみたいなのが出来ます。

class Person {
    string name;
    string address;
    int age;
public:
    Person(string name, string address, int age) 
        : name(name), address(address), age(age) {}

    friend ostream& operator<<(ostream& os, const Person& p);

};
ostream& operator<<(ostream& os, const Person& p){
    os << "名前 " << p.name << endl;
    os << "住所 " << p.address << endl;
    os << "年齢 " << p.age;
    return os;
}

int main(){

    Person person("うえしょ", "東京都、、、", 23);

    cout << person << endl;
    // 名前 うえしょ
    // 住所 東京都、、、
    // 年齢 23

    return 0;
}

上のコードを見ると出力を自分で決められるので、こちらは便利に感じるはずです。

ちなみに、friend 指定子はせっかく private で隠したもの(カプセル化)を壊してしまうので、現在では出力の時くらいでしか指定しません。

番外編

コンパイル時に計算できるものを予め計算して定数にしておくことで、 実行時の計算を減らすことができる。

何をすればいいのかと言うとクラスのすべてのメンバ関数の先頭に constexpr をつけます。
constexprを使用することで、コンパイル時に値が決定する定数、コンパイル時に実行される関数、コンパイル時にリテラルとして振る舞うクラスを定義できるらしいです。

すいません自分も詳しく理解していません。

ここまで高速化が求められるのは青色以上だと思ってます。

完成したのがこちらです。

constexpr int mod = 1000000007;
class mint {
public:
    long long x;
    constexpr mint(long long x=0) : x((x%mod+mod)%mod) {}
    constexpr mint operator-() const { 
      return mint(-x);
    }
    constexpr mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator*=(const mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    constexpr mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    constexpr mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    constexpr mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    constexpr mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    constexpr mint inv() const {
        return pow(mod-2);
    }
    constexpr mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    constexpr mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
};
ostream& operator<<(ostream& os, const mint& m){
    os << m.x;
    return os;
}

結局メンバ変数の x は if(a.x > b.x)などの比較ができるのでpublicにしました。
operator==や!=, <, > などの比較演算子をオーバーロードしたりすれば、privateでも利用できるのですが、全部書くとコードが圧迫されます。とても嫌なお気持ちですね。

比較やインクリメント、デクリメントは出来ないので、使う際は注意してください。

追記 :
また、初期化子リストを使うのが良いと話しましたが、最大限の高速化を実現するためコンストラクタは、メンバ変数 x が組み込み型というのもあり代入での初期化を行っています。
% modを2回とるより処理が早くなります。

    constexpr mint(long long x=0) {
        x = x % mod;
        if(x < 0) x += mod
    }

上のコードのように書いてましたが、初期化子での初期化をしていないので constexpr はできなかったです。
すいませんでした。
constexpr mint(long long x=0) : x((x%mod+mod)%mod) {}
のように訂正しました。

publicにしたので、出力のところはクラスの外に出しています。

【参考にさせてもらった記事】

• けんちょんさん　「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
• 熨斗さんのブログ　modint 構造体を使ってみませんか？ (C++)