結果

問題 No.1596 Distance Sum in 2D Plane
ユーザー lynmisakuralynmisakura
提出日時 2021-07-09 21:45:36
言語 C++17
(gcc 11.2.0 + boost 1.78.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 2,156 bytes
コンパイル時間 1,921 ms
使用メモリ 10,944 KB
最終ジャッジ日時 2023-02-01 22:49:54
合計ジャッジ時間 4,421 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 17 ms
10,756 KB
testcase_01 AC 18 ms
10,768 KB
testcase_02 AC 70 ms
10,876 KB
testcase_03 AC 72 ms
10,880 KB
testcase_04 AC 73 ms
10,832 KB
testcase_05 AC 69 ms
10,844 KB
testcase_06 AC 70 ms
10,860 KB
testcase_07 AC 69 ms
10,884 KB
testcase_08 AC 69 ms
10,944 KB
testcase_09 AC 70 ms
10,832 KB
testcase_10 AC 68 ms
10,764 KB
testcase_11 AC 61 ms
10,876 KB
testcase_12 AC 62 ms
10,852 KB
testcase_13 AC 61 ms
10,852 KB
testcase_14 AC 17 ms
10,764 KB
testcase_15 AC 17 ms
10,764 KB
testcase_16 AC 17 ms
10,768 KB
testcase_17 AC 17 ms
10,768 KB
testcase_18 AC 17 ms
10,836 KB
testcase_19 AC 17 ms
10,832 KB
権限があれば一括ダウンロードができます

ソースコード

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