fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 3e7;
  9. const int MOD = 1e9 + 7;
  10.  
  11. struct Item
  12. {
  13.     int a, b, c;
  14.  
  15.     Item(int a = 0, int b = 0, int c = 0) :
  16.         a(a), b(b), c(c) {};
  17. };
  18.  
  19. int n, m, k;
  20. ll fact[maxn + 10], dp[4];
  21.  
  22. ll binpow(ll a, ll b)
  23. {
  24.     a %= MOD;
  25.     ll ans = 1;
  26.     for (; b; b >>= 1, (a *= a) %= MOD)
  27.         if (b & 1)
  28.             (ans *= a) %= MOD;
  29.     return ans;
  30. }
  31. ll C(int n, int k)
  32. {
  33.     return fact[n] * binpow(fact[k] * fact[n - k], MOD - 2) % MOD;
  34. }
  35. ll num_path(int x_a, int y_a, int z_a, int x_b, int y_b, int z_b)
  36. {
  37.     int dist_x = x_b - x_a;
  38.     int dist_y = y_b - y_a;
  39.     int dist_z = z_b - z_a;
  40.     return C(dist_x + dist_y + dist_z, dist_x) * C(dist_y + dist_z, dist_y) % MOD;
  41. }
  42.  
  43. int main()
  44. {
  45.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  46.     if (fopen("BEE.INP", "r"))
  47.     {
  48.         freopen("BEE.INP", "r", stdin);
  49.         freopen("BEE.OUT", "w", stdout);
  50.     }
  51.  
  52.     cin >> n >> m >> k;
  53.     fact[0] = 1;
  54.     for (int i = 1; i <= maxn; i++)
  55.         fact[i] = i * fact[i - 1] % MOD;
  56.     vector<Item> it;
  57.     it.push_back(Item(n/3, m/3, k/3));
  58.     it.push_back(Item(2 * n/3, 2 * m/3, 2 * k/3));
  59.     it.push_back(Item(n, m, k));
  60.     for (int i = 0; i <= 2; i++)
  61.     {
  62.         dp[i] = num_path(0, 0, 0, it[i].a, it[i].b, it[i].c);
  63.         for (int j = 0; j < i; j++)
  64.             (dp[i] -= num_path(it[j].a, it[j].b, it[j].c, it[i].a, it[i].b, it[i].c) * dp[j] % MOD) %= MOD;
  65.     }
  66.  
  67.     cout << (num_path(0, 0, 0, n, m, k) - dp[2] + MOD) % MOD;
  68. }
  69.  
Success #stdin #stdout 0.18s 237916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/B4P09K
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!