Guest User

ABC - version two

a guest
Mar 16th, 2023
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream fin("adece.in");
  6. ofstream fout("adece.out");
  7.  
  8. const int mod = 1e8 + 7;
  9. const int kN = 9e3;
  10. int f[1 + kN], invf[1 + kN];
  11.  
  12. void addSelf(int &x, const int &y) {
  13.   x += y;
  14.   if (x >= mod) {
  15.     x -= mod;
  16.   }
  17. }
  18.  
  19. int add(int x, const int &y) {
  20.   addSelf(x, y);
  21.   return x;
  22. }
  23.  
  24. void multSelf(int &x, const int &y) {
  25.   x = (int64_t)x * y % mod;
  26. }
  27.  
  28. int mult(int x, const int &y) {
  29.   multSelf(x, y);
  30.   return x;
  31. }
  32.  
  33. int Pow(int x, int n) {
  34.   int ans = 1;
  35.  
  36.   while (n) {
  37.     if (n & 1) {
  38.       multSelf(ans, x);
  39.     }
  40.     multSelf(x, x);
  41.     n >>= 1;
  42.   }
  43.  
  44.   return ans;
  45. }
  46.  
  47. int invers(int x) {
  48.   return Pow(x, mod - 2);
  49. }
  50.  
  51. void computeFactorials(int n) {
  52.   f[0] = f[1] = 1;
  53.   for (int i = 2; i <= n; ++i) {
  54.     f[i] = mult(f[i - 1], i);
  55.   }
  56.  
  57.   invf[n] = invers(f[n]);
  58.   for (int i = n - 1; i >= 0; --i) {
  59.     invf[i] = mult(invf[i + 1], i + 1);
  60.   }
  61. }
  62.  
  63. int main() {
  64.   int a, b, c;
  65.   fin >> a >> b >> c;
  66.  
  67.   int n = a + b + c, m = min({a, b, c});
  68.  
  69.   computeFactorials(n);
  70.  
  71.   int res = 0;
  72.  
  73.   for (int i = 0; i <= m; ++i) {
  74.     int remA = a - i;
  75.     int remB = b - i;
  76.     int remC = c - i;
  77.     int remN = remA + remB + remC + i;
  78.  
  79.     int ways = mult(f[remN], mult(mult(invf[remA], invf[remB]), mult(invf[remC], invf[i])));
  80.  
  81.     if (i % 2 == 0) {
  82.       addSelf(res, ways);
  83.     } else {
  84.       addSelf(res, mod - ways);
  85.     }
  86.   }
  87.  
  88.   fout << res  << '\n';
  89.  
  90.   fin.close();
  91.   fout.close();
  92.  
  93.   return 0;
  94. }
Add Comment
Please, Sign In to add comment