AtCoder Beginner Contest 156 C.Rally
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( 1 0 9 + 7 ) . (10^9+7). (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 ≤ 1 0 9 2≤n≤10^9 2≤n≤109
- 1 ≤ a < b ≤ m i n ( n , 2 × 1 0 5 ) 1≤a
nab
Output Print the number of bouquets that Akari can make, modulo( 1 0 9 + 7 ) (10^9+7) (109+7). (If there are no such bouquets, print 0.)
Sample Input 1
4 1 3
Sample Output 1
7
Sample Input 2
1000000000 141421 173205
Sample Output 2
34076506
【数论|AtCoder Beginner Contest 156 C.Rally】这题不难，首先推出所有情况为 2 n ? 1 2^n-1 2n?1，减去组合数C n a C_n^a Cna? 和C n b C_n^b Cnb? 即可，套一个卢卡斯定理的模板，注意负数取模的问题，不能直接 ( a n s + m o d ) % m o d (ans+mod)\%mod (ans+mod)%mod，否则会WA，要一直加直到大于0时才取模，具体见代码：
#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll p(ll a, ll n)
{
if(n == 0) return 1;
ll x = p(a, n/2);
ll ans = x * x % mod;
if(n % 2 == 1) ans = ans *a % mod;
return ans%mod;
}ll C(ll n,ll m) {
if(n < m) return 0;
ll res = 1;
for(ll i=1;
i<=m;
i++) {
ll a = (n+i-m)%mod;
ll b = i%mod;
res = res*(a*p(b,mod-2)%mod)%mod;
}
return res;
}ll Lucas(ll n,ll m) {
if(m == 0) return 1;
return C(n%mod, m%mod) * Lucas(n/mod,m/mod)%mod;
}ll n,a,b;
int main(){
cin>>n>>a>>b;
ll ans=p(2,n)-Lucas(n,a)-Lucas(n,b)-1;
while(ans<0) {
ans+=mod;
}
cout< 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组