結果

問題 No.1596 Distance Sum in 2D Plane
コンテスト
ユーザー kanzakihikaru
提出日時 2021-07-09 22:59:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 78 ms / 2,000 ms
コード長 2,144 bytes
コンパイル時間 1,636 ms
コンパイル使用メモリ 170,256 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2024-07-01 18:04:22
合計ジャッジ時間 3,724 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <string>

#define rep(i,n) for(ll i=0;i < (n);i++)
#define rep2(i, s, n) for (ll i = (s); i < (n); i++)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define ff first
#define ss second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;

const ll INF=1000000000000000000ll;
const ll MOD=1000000007ll;
const int MAX=5100000;

using namespace std;

// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k) {
    if(n < k){return 0;};
    if(n < 0 || k < 0){return 0;};
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}

int main()
{
	cin.tie(0);	ios::sync_with_stdio(false);
  init_nCk(400000);
  ll N, M; cin >> N >> M;

  ll ans = nCk(N*2, N);
  ans *= N; ans %= MOD;
  ans *= 2; ans %= MOD;

  ll t, x, y, tmp;
  rep(i, M){
    cin >> t >> x >> y;
    if(t == 1){
      tmp = nCk(x+y, x) * nCk(2*N-x-y-1, N-y); tmp %= MOD;
      ans -= tmp; if(ans < 0){ans += MOD;}
    }
    else{
      tmp = nCk(x+y, x) * nCk(2*N-x-y-1, N-x); tmp %= MOD;
      ans -= tmp; if(ans < 0){ans += MOD;}
    }
  }

  cout << ans << endl;

  return 0;
}
0