Mod計算について

今回はAtCoderの記事です。
以前から余りの問題をやりますと言っていたので、今回はMod計算全般についてやりました。
（大変でした・・・）

ちなみに、前回勉強した貪欲法についての記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

Mod計算とは

mod計算とは、modの後にくる数字（これを法という）の余りの計算を行うことです。
高校生の数学の1年で習うやつですね。
例えば、5を13で割った余りと18を13で割った余りは同じ5なので、13を法とする世界では合同である、という感じですね。
AtCoderでは（というか競プロでは）、1000000007を法とする問題がよく出てきます。

どのように解くのか（Javaの場合）

mod計算の具体的な解き方は以下に分かりやすい記事を貼っておきましたので、こちらを見てください。
（きっと私よりずっとわかりやすいので）
qiita.com

ここでは、実際にJavaでどのように解くのかについて書きます。
まずは、自分で上記の記事を参考にして、modの四則演算、組み合わせ、逆元などに関するライブラリを作ります。
（コンテストのたびに1から書くのは絶対無理）
ちなみに、私が作ったライブラリがあるのでよかったら参考にしてください。
（バグがあるかもしれませんが）
競プロでは、Javaは本当に情報が少ないですよね。
github.com

次に、自作のライブラリを使って問題を解き、バグがないかを確認します。
実際に、比較的最近出題されたABC156のD問題 Bouquet で試してみました。
atcoder.jp

実際に解いてみたのですが、TLEやOut of Memory Errorになりまくりです。
nが大きすぎると、上の記事に書いてあるnCrではOut of Memory Errorになってしまうので、以下の記事を参考にして新しいものをライブラリに追加しました。
こちらの記事では、n, rの大きさによってどの手法を使うべきかきれいに場合分けされています。
drken1215.hatenablog.com

ようやく、TLEやOut of Memory Errorにならない正解を見つけたのがこちらです。
自作のメソッドの仕様は上に貼ったライブラリの中身を見てもらえると嬉しいです。

import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();

		ComInit_bign(n, Math.max(a, b));
		long ans = modpow(2, n);
		ans = sub(ans, Com_bign(n, 0));
		ans = sub(ans, (Com_bign(n, a) + Com_bign(n, b)));

		System.out.println(ans);
	}
}

四則演算（上のsubなど）は原則自作のメソッドを用います。
あと、累乗についても自作のmodpowというメソッドを用います。
（これを用いないとTLEします。二分累乗法を使っています）

解き方については、nC0+nC1+nC2+...+nCn=2^nになることを利用して、（二項定理）
そこからnC0とnCa、nCbを引きます。
a, b <= 2*10^5 なので、Out of Memory Errorにならずに解けます。

ということで、今回の記事は終了です。
やはり重かったですね。
とても疲れましたが、いよいよ明日（0時回ったので正確には今日）の21時からABC165が始まるので明日も頑張りたいです。