ABC156「Bouquet」

Bouquet

考えたこと

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

解法

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

コード

#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っていう便利なライブラリあるっぽいけど、剰余の理解が微妙な状態で使うとだめそう