fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define MP make_pair
  7. #define PB push_back
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define SZ(a) int(a.size())
  11. #define ALL(a) a.begin(), a.end()
  12. #define MS(a, v) memset(a, v, sizeof a)
  13. #define REP(i, n) for(int i = 0; i < n; ++ i)
  14. #define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
  15. #define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
  16. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".ans", "w", stdout)
  17.  
  18. template<class X, class Y>
  19.         bool maximize(X & x, const Y & y){
  20.                 if(x < y){
  21.                         x = y;
  22.                         return true;
  23.                 }
  24.                 else return false;
  25.         }
  26.  
  27. template<class X, class Y>
  28.         bool minimize(X & x, const Y & y){
  29.                 if(x > y){
  30.                         x = y;
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.  
  36. const int MAXN = 200005;
  37. const int MOD = 1e9 + 7;
  38. const ll INF = 1e18;
  39.  
  40. int sum(int a, int b){
  41.         return a + b >= MOD ? a + b - MOD : a + b;
  42. }
  43.  
  44. void add(ll &a, int b){
  45.         a += b;
  46.         if(a >= MOD) a -= MOD;
  47. }
  48.  
  49. int Pow(int a, int b){
  50.         int res = 1;
  51.         while(b > 0){
  52.                 if(b & 1){
  53.                         res = 1ll * res * a % MOD;
  54.                 }
  55.                 b >>= 1; a = 1ll * a * a % MOD;
  56.         }
  57.         return res;
  58. }
  59.  
  60. int n, a[MAXN], b[MAXN], C[4004][4004];
  61.  
  62. namespace sub1{
  63.         bool check(void){
  64.                 return n <= 2000;
  65.         }
  66.  
  67.         void solve(void){
  68.                 ll res = 0;
  69.                 FOR(i, 1, n){
  70.                         FOR(j, i + 1, n){
  71.                                 int x = a[i] + a[j];
  72.                                 int y = b[i] + b[j];
  73.                                 add(res, C[x + y][x]);
  74.                         }
  75.                 }
  76.                 cout << res;
  77.         }
  78. }
  79.  
  80. namespace sub2{
  81.         bool check(void){
  82.                 return *max_element(a + 1, a + n + 1) <= 100 && *max_element(b + 1, b + n + 1) <= 100;
  83.         }
  84.  
  85.         int dd[101][101];
  86.  
  87.         void solve(void){
  88.                 ll res = 0;
  89.                 FOR(i, 1, n)
  90.                         ++ dd[ a[i] ][ b[i] ];
  91.  
  92.                 int u2 = Pow(2, MOD - 2);
  93.  
  94.                 FOR(i, 1, 100) FOR(j, 1, 100) if(dd[i][j]){
  95.                         FOR(u, 1, 100) FOR(v, 1, 100) if(dd[u][v]){
  96.                                 ll c1 = dd[i][j], c2 = dd[u][v];
  97.                                 int x = i + u, y = j + v;
  98.                                 ll val = C[x + y][y];
  99.                                 if(u == i && v == j)
  100.                                         add(res, val * ((c1 * (c1 - 1) / 2) % MOD) % MOD);
  101.                                 else
  102.                                         add(res, val * c1 % MOD * c2 % MOD);
  103.                         }
  104.                 }
  105.                 cout << res * u2 % MOD;
  106.         }
  107. }
  108.  
  109.  
  110. void solve(void){
  111.         cin >> n;
  112.         FOR(i, 1, n) cin >> a[i] >> b[i];
  113.  
  114.         FOR(i, 0, 2000) C[i][0] = 1;
  115.         FOR(i, 1, 2000)
  116.                 FOR(j, 1, i)
  117.                         C[i][j] = sum(C[i - 1][j], C[i - 1][j - 1]);
  118.  
  119. //        if(sub1 :: check())
  120. //                return sub1 :: solve();
  121.         if(sub2 :: check())
  122.                 return sub2 :: solve();
  123. }
  124.  
  125. int main(void){
  126.  
  127.         ios_base :: sync_with_stdio(0);
  128.         cin.tie(0); cout.tie(0);
  129.  
  130.         #define TaZinh "test"
  131.  
  132.         if(fopen(TaZinh".inp", "r"))
  133.                 TSun(TaZinh);
  134.  
  135.         int Sun = 1;
  136. //        cin >> Sun;
  137.         REP(love, Sun) solve();
  138.  
  139.         return 0;
  140. }
  141.  
Success #stdin #stdout 0.01s 34684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ypmgi3
language:
C++ (gcc 8.3)
created:
10 hours 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!