結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
![]() |
提出日時 | 2021-07-09 21:52:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 455 ms / 2,000 ms |
コード長 | 2,068 bytes |
コンパイル時間 | 1,647 ms |
コンパイル使用メモリ | 172,528 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-07-01 16:09:41 |
合計ジャッジ時間 | 8,133 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) #define debug(output) if(debugFlag)cout<<#output<<"= "<<output<<endl using lint = long long; typedef pair<int,int> P; const bool debugFlag=true; const lint linf=1e18+7; const lint inf=1e9+7; const int MOD=1000000007; struct Nums{ long long n; vector<long long> kaijo; Nums(int N){ n=N; kaijo.push_back(1); for(long long i=1;i<=n;i++){ kaijo.push_back((kaijo[i-1]*i)%MOD); } } long long myPow(long long x, long long n, long long m){ if(n == 0) return 1; if(n % 2 == 0) return myPow(x * x % m, n / 2, m); else return x * myPow(x, n - 1, m) % m; } long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } long long comb(long long N,long long K,long long rest){ if(N<0||K<0)return 0; if(N<K)return 0; long long res=kaijo[N]*modinv(kaijo[K],rest)%rest; res*=modinv(kaijo[N-K],rest); res%=rest; return res; } long long comb2(long long N,long long K,long long rest){ // O(K)で2項係数を返す if(N<0||K<0)return 0; if(N<K)return 0; long long res=modinv(kaijo[K],rest); for(long long i=0;i<K;++i){ res*=(N-i)%rest;res%=rest; } return res; } }; signed main(){ int n,m;cin>>n>>m; vector<int> t(m),x(m),y(m); rep(i,m)cin>>t[i]>>x[i]>>y[i]; Nums lib(n*2+10); lint res=lib.comb(2*n,n,MOD)*2*n%MOD; rep(i,m){ lint sub=lib.comb(x[i]+y[i],x[i],MOD); if(t[i]==1)sub*=lib.comb(2*n-x[i]-y[i]-1,n-x[i]-1,MOD); else sub*=lib.comb(2*n-x[i]-y[i]-1,n-y[i]-1,MOD); sub%=MOD; res+=MOD-sub; res%=MOD; } cout<<res<<"\n"; return 0; }