ABC 156-D: Bouquet

작성일

https://atcoder.jp/contests/abc156/tasks/abc156_d

  • 2월동안 187문제 풀기(지난달 누적 87개) (54/187)
  • 조합을 구하는 가장 기본적인 방식을 놓치고 있었다니 -_-…
    • $\displaystyle n!(r!(n-r)!)^{-1}=\sum_{k=n}^{n-r+1}k(r!)^{-1}$
  • 뼈저리게 반성해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const LL M = 1000000007;
 
inline LL mul(LL a, LL b) {
  return (a*b)%M;
}
 
inline LL add(LL a, LL b) {
  return (a+b)%M;
}
 
LL ppow(LL a, LL e) {
  LL ans = 1;
  while(e) {
    if(e&1) ans = mul(ans, a);
    a = mul(a,a);
    e /= 2;
  }
  return ans;
}
 
LL n, a, b;
int main() {
  cin >> n >> a >> b;
  LL pp = ppow(2, n);
 
  LL c1 = 1;
  LL n1 = n;
  for(int i = 0; i < a; i++)
    c1 = mul(c1, n1--);
 
  LL af = 1;
  for(int i = 1; i <= a; i++)
    af = mul(af, i);
  LL nc1 = mul(c1, ppow(af, M-2));
 
  LL c2 = 2;
  LL n2 = n;
  for(int i = 0; i < b; i++)
    c2 = mul(c2, n2--);
 
  LL bf = 2;
  for(int i = 1; i <= b; i++)
    bf = mul(bf, i);
  LL nc2 = mul(c2, ppow(bf, M-2));
  cout << (2*M + pp - nc1 - nc2 - 1) % M;
}