算法
(对立事件、快速幂、组合数取模) $O(a + b)$
考虑这个问题的对立事件,即:恰选了 $a$ 种花和恰选了 $b$ 种花的方案数总和
所以 $ans = 2^N - 1 - nCa - nCb$ 。
$nCa$ 可以变为 $\frac{\displaystyle\prod_{i = 0}^{a - 1} (n - i)}{a!}$,所以可以 $O(a)$ 求出。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using ll = long long;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll 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;
}
};
mint choose(int n, int a) {
mint x = 1, y = 1;
rep(i, a) {
x *= n - i;
y *= i + 1;
}
return x / y;
}
int main() {
int n, a, b;
cin >> n >> a >> b;
mint ans = mint(2).pow(n);
ans -= 1;
ans -= choose(n, a);
ans -= choose(n, b);
cout << ans.x << '\n';
return 0;
}