原题链接：https://atcoder.jp/contests/abc156/tasks/abc156_d

题目描述

Akari has n kinds of flowers, one of each kind.
She is going to choose one or more of these flowers to make a bouquet.
However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.
How many different bouquets are there that Akari can make?
Find the count modulo (1e9+7).
Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.

数据范围

All values in input are integers.
2≤n≤1e9
1≤a<b≤min(n,2×1e5)

输入

Input is given from Standard Input in the following format:
n a b

输出

Print the number of bouquets that Akari can make, modulo (1e9+7). (If there are no such bouquets, print '0'.)

样例输入

4 1 3

样例输出

7

样例输入

1000000000 141421 173205

样例输出

34076506

首先，我们需要计算$C(n,1)+C(n,2)+C(n,3)+...+C(n,n)$，由组合数的性质可知，该式为$n!-1$。
故我们需要输出的是$n!-1-C(n,a)-C(n,b)$模$1e9+7$的结果。
由于$a$和$b$可能很大，所以我们需要使用逆元法来求得$C(n,a)$和$C(n,b)$。
代码如下：

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define fast_io()                \
    ios::sync_with_stdio(false); \
    std::cin.tie(0);
#define mod 1000000007
typedef long long ll;
typedef long double ld;
using namespace std;
ll qpow(ll a,ll b,ll m)
{
    ll ans=1;
    ll base = a;
    while(b>0)
    {
        if(b&1)
            ans = (ans * base) % m;
        base = (base * base) % m;
        b >>= 1;
    }
    return ans;
}
ll C(ll n,ll m)
{
    ll ans = 1;
    for (ll i = 1;i<=m; i++)
    {
        ll tmp;
        tmp = (n - i + 1) % mod;
        ans *= (tmp * qpow(i, mod - 2, mod)) % mod;
        ans %= mod;
    }
    return ans;
}

int main()
{
    fast_io();
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans;
    ans = qpow(2, n, mod) - 1;
    ans=(ans+mod-C(n, a))%mod;
    ans=(ans+mod-C(n, b))%mod;
    cout << ans;
    system("pause");
    return 0;
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/28.html
最后修改时间：2020-07-27 13:38:31
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！