Bouquet

考えたこと

よくわからんから実験した
- a, b考えずに全部足すと2^n本になる（これ、実験しなくても普通に考えて2^nだった）
- だから、そこからnCaとnCbを引けばよさそう
- 答えは2^n - nCa - nCb - 1となる。-1は0本の分
あまりの計算を考える
- 2^nは繰り返し二乗法でいける
- nCaはaの制約が10^5までだから掛け算でできそう。割り算が発生するから、フェルマーの小定理で逆元かけるやつをする。
- はい天才
なんかバグる
- ふて寝した

解法

求めるもの何か？
- $2^n - 1$が全体本数
- そこからa本選ぶ場合とb本選ぶ場合を考えれば良い
- つまり、求めるものは$2^n - 1 - nCa - nCb$
$2^n-1$を求める
- nは非常に大きいが、繰り返し二乗法でにより$O(logN)$で求められる
nCkを求める
- $nCk = \frac{n(n-1)...(n-k+1)}{k(k-1)...1}$となる
- 計算量は$O(k)$だから大丈夫。
- 計算自体は、「分母×分子の逆元」で計算できる
- 逆元はフェルマーの小定理で求まる
負の剰余について
- 負数の剰余を計算してはならないっていう記事によると、負の剰余をプログラムで計算するときはちょっとめんどい
- 記事の内容を完全理解したわけじゃないけど、とりあえず剰余の計算は正の値で計算すればよさそう

コード

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9+7;

// a^bを返す
long long Pow(long long a, long long b) {
	long long ret = 1;
	while (b > 0) {
		if (b & 1) {
			ret = (ret % mod) * (a % mod) % mod;
		}
		a = (a % mod) * (a % mod) % mod;
		b /= 2;
	}

	return ret % mod;
}

// nCkを返す
long long nCk(long long n, long long k) {
	long long bunbo = 1, bunshi = 1;
	for (int ki = 1; ki <= k; ki++) {
		bunbo *= ki;
		bunshi *= n - ki + 1;
		bunbo %= mod;
		bunshi %= mod;
	}

	return bunshi * Pow(bunbo, mod - 2) % mod;
}

int main() {
	long long n, a, b;
	cin >> n >> a >> b;

	// 全体の本数
	long long ans = Pow(2, n) - 1;

	// nCaの分を引く
	ans -= nCk(n, a);
	ans %= mod;

	// nCbの分を引く
	ans -= nCk(n, b);
	ans %= mod;

	// ansをmodの範囲に収める → modを足して正の値にする → %modを計算する
	ans = ((ans % mod) + mod) % mod;

	cout << ans << endl;

	return 0;
}

感想

mod上で$\frac{a}{b}$するの、Pとbが互いに素であればバグらないと思ってたけど違った
- $\frac{a}{b}$が整数にならない場合、バグる。
- mod上では整数しか扱わないっぽい
- だから、mod上では普通に割るんじゃなくて逆元をかけた方が良さそう
負の剰余を計算すると面倒なことになるから、とりあえず正の値にしてから剰余計算するとよさそう
modintっていう便利なライブラリあるっぽいけど、剰余の理解が微妙な状態で使うとだめそう