Advertisement
Guest User

Untitled

a guest
Jul 16th, 2016
298
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. const int MOD = (int)1e9 + 7;
  10. int add(int x, int y)
  11. {
  12.     x += y;
  13.     if (x >= MOD) return x - MOD;
  14.     return x;
  15. }
  16. int sub(int x, int y)
  17. {
  18.     x -= y;
  19.     if (x < 0) return x + MOD;
  20.     return x;
  21. }
  22. int mult(int x, int y)
  23. {
  24.     return ((ll)x * y) % MOD;
  25. }
  26. int bin_pow(int x, int p)
  27. {
  28.     if (p == 0) return 1;
  29.     if (p == 2 || (p & 1)) return mult(x, bin_pow(x, p - 1));
  30.     return bin_pow(bin_pow(x, p / 2), 2);
  31. }
  32. int rev(int x)
  33. {
  34.     return bin_pow(x, MOD - 2);
  35. }
  36.  
  37. const int N = 200100;
  38. const int K = 4010;
  39. const int Z = 2002;
  40. int n;
  41. int a[N][2];
  42. int C[K][K];
  43. ll b[K];
  44. int f[2 * K], rf[2 * K];
  45. int ans = 0;
  46.  
  47. void init()
  48. {
  49.     f[0] = 1;
  50.     for (int i = 1; i < 2 * K; i++)
  51.         f[i] = mult(f[i - 1], i);
  52.     rf[2 * K - 1] = rev(f[2 * K - 1]);
  53.     for (int i = 2 * K - 1; i > 0; i--)
  54.         rf[i - 1] = mult(rf[i], i);
  55.  
  56.    
  57.     for (int i = 0; i < K; i++)
  58.         C[i][0] = C[i][i] = 1;
  59.     for (int i = 1; i < K; i++)
  60.         for (int j = 1; j < i; j++)
  61.             C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
  62.  
  63.     return;
  64. }
  65.  
  66. void read()
  67. {
  68. /* 
  69.     n = 200000;
  70.     for (int i = 0; i < n; i++)
  71.         a[i][0] = a[i][1] = 2000;
  72.     */
  73.    
  74.    
  75.     scanf("%d", &n);
  76.     for (int i = 0; i < n; i++)
  77.         for (int j = 0; j < 2; j++)
  78.             scanf("%d", &a[i][j]);
  79.    
  80.  
  81.     return;
  82. }
  83.  
  84. void solve(int x, int y)
  85. {
  86.     /*
  87.     for (int i = -x; i <= y; i++)
  88.         b[Z - i] = add(b[Z - i], C[x + y][x + i]);
  89.     */
  90.    
  91.     for (int i = -x; i <= y; i++)
  92.         b[Z - i] += C[x + y][x + i];
  93.    
  94.     return;
  95. }
  96.  
  97. int getC(int n, int k)
  98. {
  99.     return mult(f[n], mult(rf[k], rf[n - k]));
  100. }
  101.  
  102. int main()
  103. {
  104. //  freopen("input.txt", "r", stdin);
  105. //  freopen("output.txt", "w", stdout);
  106.  
  107.     init();
  108.  
  109.     read();
  110.  
  111.     for (int i = 0; i < n; i++)
  112.         solve(a[i][0], a[i][1]);
  113.  
  114.     for (int i = -Z; i <= Z; i++)
  115.         b[Z + i] %= MOD;
  116.  
  117.     for (int i = -Z; i <= Z; i++)
  118.         ans = add(ans, mult(b[Z + i], b[Z - i]));
  119.  
  120.     for (int i = 0; i < n; i++)
  121.         ans = sub(ans, getC(2 * (a[i][0] + a[i][1]), 2 * a[i][0]));
  122.  
  123.     if (ans & 1) ans += MOD;
  124.     ans /= 2;
  125.  
  126.     printf("%d\n", ans);
  127.  
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement