Advertisement
Guest User

Untitled

a guest
Oct 18th, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 1000000007;
  8. const int valMax = 2 * 100005;
  9.  
  10. long long fact[valMax];
  11.  
  12. long long power(long long base, long long exp)
  13. {
  14.     if(exp == 0)
  15.         return 1;
  16.     if(exp % 2 == 0)
  17.     {
  18.         long long x = power(base, exp / 2);
  19.         return (x * x) % MOD;
  20.     }
  21.     return (base * power(base, exp - 1)) % MOD;
  22. }
  23.  
  24. inline long long invers(long long x)
  25. {
  26.     return power(x, MOD - 2);
  27. }
  28.  
  29. void CalcFact()
  30. {
  31.     fact[0] = 1;
  32.     for(int i = 1; i < valMax; ++i)
  33.         fact[i] = (fact[i-1] * i) % MOD;
  34. }
  35.  
  36. long long comb(long long n, long long k)
  37. {
  38.     return (fact[n] * invers((fact[k] * fact[n-k]) % MOD)) % MOD;
  39. }
  40.  
  41. inline long long Paths(int x, int y) //drumuri de la 1,1 la x,y
  42. {
  43.     return comb(x + y - 2, x - 1);
  44. }
  45.  
  46. int main()
  47. {
  48.     CalcFact();
  49.     int h, w, n;
  50.     cin >> h >> w >> n;
  51.     vector<pair<int, int> > black(n);
  52.     for(int i = 0; i < n; ++i)
  53.         cin >> black[i].first >> black[i].second;
  54.     n++;
  55.     black.push_back(make_pair(h, w));
  56.     sort(black.begin(), black.end());
  57.     vector<long long> dp(n);
  58.     dp[0] = Paths(black[0].first, black[0].second);
  59.     for(int i = 1; i < n; ++i)
  60.     {
  61.         dp[i] = Paths(black[i].first, black[i].second);
  62.         for(int j = 0; j < i; ++j)
  63.         {
  64.             dp[i] -= (dp[j] * Paths(black[i].first - black[j].first + 1, black[i].second - black[j].second + 1)) % MOD;
  65.             if(dp[i] < 0)
  66.                 dp[i] += MOD;
  67.         }
  68.     }
  69.     cout << dp.back();
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement