运行要求
运行时间限制: 2sec
内存限制: 1024MB
未经允许，不得许转载
原题链接
题目
小明手上有n种花，每一种花都有一束。
从这些花种选择一束以上的花做花束。
但是，小明讨厌a和b两个数字。花束数量和a或b这两个数字相同的花束不能制作。
求小明能够制作多少花束。
结果取和10^9+7相除取mod的结果
在这里，如果有两个花束。花束A,花束B。花束A里用到的花在花束B里不存在的花，花束A和花束B算作不同的花束。
输入前提条件
所有的输入均为整数 2 <=n <= 10^9 1 <=a <= b <= min(n,2*10^5)输入
输入按照以下形式标准输入
n a b
输出
输出小明可以制作的花束的种类。结果取(10^9+7)的mod。
例1
输入
4 1 3
输出
7
小明讨厌数字1，3。在这种情况下，小明可以制作2朵花，或者4朵花的花束
在4朵花中选择2多花的选择方法有6种
在4朵花中选择4朵花的选择方法有1种
总共加起来有6+1=7种
例2
输入
1000000000 141421 173205
输出
34076506
读懂题目
有n多花，每一朵花只有一种
可以把这题抽象成排列组合的问题
n个球，每个球不一样，从n个球里取m个球，总共有C(n,m)个取法
解题思路
从n个球里取a个球不可以，从n个球里取a个球的取法有c（n，a）个取法
从n个球里取b个球不可以，从n个球里取b个球的取法有c（n，b）个取法
那么从n个球种取1，2，3，4，5...n的取法有多少种呢
每个球有取和被取两种状态，所以一共有2^n的取法
2^n个取法中，包括n个球都不取的情况，所以符合要求的取法数量是2^n-1
那么答案就是2^n-1 - c(n,a) - c(n,b)
下面就是比较费劲的地方了
n可以高达10^9
所以我们要求2^n和c(n,a)的花普通的计算根本不可能
题目要求我们取10^9+7的mod
我们先求2^n
官方给出的方法是“快速幂”的算法
我会在下面贴出“快速幂”的算法的python实现
但是python自带的pow方法，可以传第三个参数mod。当指明第3个参数的时候，表示每做一次阶乘运算都会与mod取mod。
我翻看了下pow方法的注释
def pow(*args, **kwargs): # real signature unknown """ Equivalent to x**y (with two arguments) or x**y % z (with three arguments) Some types, such as ints, are able to use a more efficient algorithm when invoked using the three argument form. """ pass
当传如第3个参数的时候，将会使用一些非常高效的算法。
实际运用的时候，也是非常快的。我们权且认为python自带的pow传入第3个参数mod的时候，使用了快速幂的方法。
下一个难点
c(n,a) =
n (n - 1) (n - 2) ... + (n - a + 1) / a!
我们设
X = n (n - 1) (n - 2) ... + (n - a + 1)
Y = a!
我们需要求出 X % (10^9 + 7)
每乘以下做一下mod运算就好
我们需要求出 1/Y % ((10^9 + 7))
这可如何是好，mod运算里面的除法，不像mod运算里面的乘法那样，单纯的除一次，去一下mod
根据费马小定理
对于mod=10^9+7这样的数
所以我们需要求得(1/Y) % mod
只需要求得到Y^(mod-2) % mod
对于Y^(mod-2)我们用快速幂实现。python自带的pow函数能够为我们实现这一点。
代码
快速幂
https://blog.csdn.net/ggdhs/a...
AC结果
n, a, b = 10, 2, 3 n, a, b = map(int,input().split()) def jiecheng(start, end): res = 1 for i in range(start, end + 1): res = (res * i) % (10 ** 9 + 7) return res def comb(n, a): X = jiecheng(n - a + 1, n) % (10**9 + 7) Y = jiecheng(1, a) S = X * pow(Y, 10 ** 9 + 5, 10 ** 9 + 7) return S def calculate(n, a, b): s = pow(2, n, 10 ** 9 + 7) - 1 s1 = comb(n, a) s2 = comb(n, b) res = s - s1 - s2 res = res % (10**9 + 7) return res result = calculate(n, a, b) print(result)
总结
本题考察对排列组合的运用，对快速幂的运用，对费马小定理的应用。
※ 另外，我会在我的微信个人订阅号上推出一些文章，欢迎关注
