Advertisement
Guest User

Untitled

a guest
Mar 1st, 2020
225
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <ctime>
  6. #include <iomanip>
  7. #include <numeric>
  8. #include <cmath>
  9. using namespace std;
  10. #define ll long long
  11. #define endl '\n'
  12. const int MAX = 2e5 + 4;
  13. const int MOD = 1e9 + 7;
  14. // Extended Euclidean algorithm
  15. int xGCD(int a, int b, int& x, int& y) {
  16. if (b == 0) {
  17. x = 1;
  18. y = 0;
  19. return a;
  20. }
  21.  
  22. int x1, y1, gcd = xGCD(b, a % b, x1, y1);
  23. x = y1;
  24. y = x1 - (long long)(a / b) * y1;
  25. return gcd;
  26. }
  27. ll fast_power(ll base, ll power)
  28. {
  29. ll result = 1;
  30. while (power)
  31. {
  32. if (power & 1)
  33. result = (result * base) % MOD;
  34. base = (base * base) % MOD;
  35. power /= 2;
  36. }
  37. return result;
  38. }
  39. ll binomialCoeff(int n, int k)
  40. {
  41. ll res = 1;
  42. if (k > n - k) k = n - k;
  43. for (int i = 0; i < k; i++)
  44. {
  45. res = res * (n - i) % MOD;
  46. res = res / (i + 1) % MOD;
  47. }
  48. return res;
  49. }
  50. int main()
  51. {
  52. ios_base::sync_with_stdio(false);
  53. cin.tie(0);
  54. int n, a, b;
  55. cin >> n >> a >> b;
  56. int result = fast_power(2, n) - 1;
  57. result -= binomialCoeff(n, a);
  58. result -= binomialCoeff(n, b);
  59.  
  60. cout << result;
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement