快速幂+组合数的经典问题

title: 快速幂+组合数的经典问题
date: 2020-04-22 10:51:53
tags:
categories: 算法

组合数，快速幂，

D - Bouquet
Time limit : 2sec / Memory limit : 1024MB

Score : 400 points

Problem Statement
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 (109+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.

Constraints
All values in input are integers.
2≤n≤109
1≤a<b≤[textrm]min(n,2×105)
Input
Input is given from Standard Input in the following format:

n a b
Output
Print the number of bouquets that Akari can make, modulo (109+7). (If there are no such bouquets, print 0.)

Sample Input 1
Copy
4 1 3
Sample Output 1
Copy
7
In this case, Akari can choose 2 or 4 flowers to make the bouquet.

There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.

Sample Input 2
Copy
1000000000 141421 173205
Sample Output 2
Copy
34076506
Print the count modulo (109+7).

//快速幂模版  适用于base^power%m

typedef long long ll;
ll fastpower(ll base,ll power,ll m){
    ll result = 1;
    while(power>0){
        if(power & 1){
            result=result*base%m;
        }
        power>>=1;
        base=base*base%m;
    }
    return result;
}

小伙伴们要是还不会快速幂的话点这里（超详细的）：
https://blog.csdn.net/qq_19782019/article/details/85621386

了解了快速幂，我们就开始啦：

Akari 有 n 种不同的花，她可以选择其中一种或多种花做成花束。但是 Akari 不喜欢花的种数恰好为 a 或 b 的花束。求出她组合花的合法方案总数，对 10^9+7 取模。

答案应该是：c(n,1)+......c(n,n),

因为 c(n,0)+...c(n,n)=2^n;

所以推出公式：ans=(2^n)-C(n,a)-C(n,b)-1；

下面就是组合数了，这个也算是一个比较难的点：