fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ii pair <int , int>
  9. #define iii pair <int , ii>
  10. #define se second
  11. #define fi first
  12. #define all(v) (v).begin() , (v).end()
  13. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  14. #define bit(x,i) (((x) >> (i)) & 1LL)
  15. #define flip(x,i) ((x) ^ (1LL << (i)))
  16. #define ms(d,x) memset(d , x , sizeof(d))
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22. #define prev __prev
  23. #define next __next
  24. #define sitingfake 1
  25. #define orz 1
  26. //constant
  27.  
  28. const long long mod = 1e7 + 1203;
  29. const long long linf = 4557430888798830399LL;
  30. const long long nlinf = -4485090715960753727LL;
  31. const int inf = 1061109567;
  32. const int ninf = -1044266559;
  33. const int dx[] = {0 , -1 , 0 , 1};
  34. const int dy[] = {-1 , 0 , 1 , 0};
  35.  
  36. template<typename T> bool maximize(T &a, const T &b)
  37. {
  38.     if(a < b) {a = b; return 1;}
  39.     return 0;
  40. }
  41.  
  42. template<typename T> bool minimize(T &a, const T &b)
  43. {
  44.     if(a > b) {a = b; return 1;}
  45.     return 0;
  46. }
  47.  
  48. void Plus(ll & a ,ll b)
  49. {
  50.     b %= mod;
  51.     a += b;
  52.     if(a < 0) a += mod;
  53.     a %= mod;
  54.     return;
  55. }
  56.  
  57. void Mul(ll & a, ll b)
  58. {
  59.     (a *= (b % mod)) %= mod;
  60.     return;
  61. }
  62.  
  63. //code
  64. const int maxn = 4e6 + 7;
  65.  
  66. int n , m , p , q;
  67.  
  68. ll fact[maxn] , inv[maxn];
  69.  
  70. ll fastpow(ll n , ll p)
  71. {
  72.     if(p == 1) return n;
  73.     if(p == 0) return 1;
  74.  
  75.     ll tmp = fastpow(n , p >> 1LL);
  76.  
  77.     Mul(tmp , tmp);
  78.  
  79.     if(p & 1) Mul(tmp , n);
  80.  
  81.     return tmp;
  82. }
  83.  
  84. void init()
  85. {
  86.     const int Lim = 4e6;// set the limit here
  87.     fact[0] = 1;
  88.  
  89.     for(int i = 1; i <= Lim; i++)
  90.     {
  91.         fact[i] = (fact[i - 1] *1ll * i) % mod;
  92.     }
  93.  
  94.     inv[Lim] = fastpow(fact[Lim] , mod - 2);
  95.  
  96.     for(int i = Lim - 1; i >= 0; i--)
  97.     {
  98.         inv[i] = ((i + 1) *1ll * inv[i + 1]) % mod;
  99.     }
  100. }
  101.  
  102. ll C(int k , int n)
  103. {
  104.     if(k < 0) return 0;
  105.     if(k > n) return 0;
  106.     if(n < 0) return 0;
  107.     return (((fact[n] * inv[k]) % mod) * inv[n - k]) % mod;
  108.  
  109. }
  110.  
  111. /**
  112. C[k][n] = C[k-1][n-1] + C[k][n-1]
  113. C[0][n] = 1
  114. C[n][n] = 1
  115. pascal triangle
  116. **/
  117.  
  118. ll dp[4004];
  119.  
  120. ii banned[maxn];
  121.  
  122. void solve(void)
  123. {
  124.     cin >> n >> m >> p >> q;
  125.  
  126.     for(int i = 1; i <= p; i++)
  127.     {
  128.         cin >> banned[i].fi >> banned[i].se;
  129.     }
  130.     sort(banned + 1 , banned + p + 1);
  131.     init();
  132.     for(int i = 1; i <= p; i++)
  133.     {
  134.         dp[i] = C(banned[i].fi - 1 , banned[i].fi + banned[i].se - 2);
  135.         for(int j = i - 1; j >= 1; j--)
  136.         {
  137.             if(banned[j].se <= banned[i].se)
  138.             {
  139.                 Plus(dp[i] , -dp[j] * C(banned[i].fi - banned[j].fi , banned[i].fi + banned[i].se - banned[j].fi - banned[j].se));
  140.             }
  141.         }
  142.     }
  143.     while(q--)
  144.     {
  145.         int u , v; cin >> u >> v;
  146.  
  147.         ll cur = C(u - 1 , u + v - 2);
  148.  
  149.         for(int i = 1; i <= p ; i++)
  150.         {
  151.             if(banned[i].fi <= u && banned[i].se <= v)
  152.             {
  153.                 Plus(cur , -dp[i] * C(u - banned[i].fi , u + v - banned[i].fi - banned[i].se));
  154.             }
  155.         }
  156.         cout << cur << " ";
  157.     }
  158. }
  159. /**
  160. **/
  161. signed main()
  162. {
  163.    ios_base::sync_with_stdio(0);
  164.    cin.tie(0);
  165.    cout.tie(0);
  166.  
  167.    #define task "walk"
  168.  
  169.    if(fopen(task".inp","r"))
  170.    {
  171.        freopen(task".inp","r",stdin);
  172.        freopen(task".out","w",stdout);
  173.    }
  174.  
  175.    int tc = 1;
  176. //   cin >> tc;
  177.    while(tc--) solve();
  178.  
  179. //   execute;
  180. }
  181.  
  182.  
  183.  
  184.  
Success #stdin #stdout 0.05s 97392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hAjD2z
language:
C++14 (clang 8.0)
created:
3 days 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!