結果

問題 No.1596 Distance Sum in 2D Plane
ユーザー lynmisakuralynmisakura
提出日時 2021-07-09 21:45:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 120 ms / 2,000 ms
コード長 2,156 bytes
コンパイル時間 4,739 ms
コンパイル使用メモリ 201,020 KB
最終ジャッジ日時 2025-01-22 21:22:52
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

// code by lynmisakura. wish to be accepted!
#include<bits/stdc++.h>
using namespace std;

#define REP(i,N) for(int i = 0;i < N;i++)
using ll = long long;

#include<atcoder/modint>
using mint = atcoder::modint1000000007;
namespace lyn{
  struct Binom{
    std::vector<std::vector<int64_t>> C;
    Binom(int MAX_N){
      C = std::vector<std::vector<int64_t>>(MAX_N,std::vector<int64_t>(0));
      for(int i = 0;i < MAX_N;i++)C[i].resize(MAX_N,0);
      for(int i = 1;i < MAX_N;i++){
        for(int j = 1;j < MAX_N;j++){
          C[i][j] = (j==0||j==i ? 1LL : C[i-1][j-1]+C[i-1][j]);
        }
      }
    }
    int64_t coef(int n,int k){
      return C[n+1][k+1];
    }
  };
  const int BINOM_MAX = 1e6+10;
  struct Binom998244353{
    using mint = atcoder::modint998244353;
    std::vector<mint> F,Finv;
    Binom998244353(){
      F.assign(BINOM_MAX,1);
      Finv.assign(BINOM_MAX,1);
      for(int i = 2;i < BINOM_MAX;i++) F[i] = F[i-1] * mint(i);
      Finv[BINOM_MAX-1] = F[BINOM_MAX-1].inv();
      for(int i = BINOM_MAX - 2;i >= 1;i--) Finv[i] = Finv[i+1] * mint(i+1);
    }
    mint coef(int n,int r){
      if(n < 0 || r < 0 || n < r) return 0;
      else return F[n] * Finv[r] * Finv[n - r];
    }
  };
  struct Binom1000000007{
    using mint = atcoder::modint1000000007;
    std::vector<mint> F,Finv;
    Binom1000000007(){
      F.assign(BINOM_MAX,1);
      Finv.assign(BINOM_MAX,1);
      for(int i = 2;i < BINOM_MAX;i++) F[i] = F[i-1] * mint(i);
      Finv[BINOM_MAX-1] = F[BINOM_MAX-1].inv();
      for(int i = BINOM_MAX - 2;i >= 1;i--) Finv[i] = Finv[i+1] * mint(i+1);
    }
    mint coef(int n,int r){
      if(n < 0 || r < 0 || n < r) return 0;
      else return F[n] * Finv[r] * Finv[n - r];
    }
  };
}
int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  
  int N,M;
  cin >> N >> M;
  
  lyn::Binom1000000007 B;

  mint ans = mint(2*N) * B.coef(2*N,N);

  REP(i,M){
    int t,x,y;
    cin >> t >> x >> y;
    if(t == 1){
      ans -= B.coef(x+y,x)*B.coef(N-y+(N-1-x),N-y);
    }else{
      ans -= B.coef(x+y,x)*B.coef((N-1-y)+(N-x),N-x);
    }
  }

  cout << ans.val() << '\n';

}
0