結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー | kenta255 |
提出日時 | 2021-07-10 01:26:21 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 1,146 bytes |
コンパイル時間 | 2,172 ms |
コンパイル使用メモリ | 202,156 KB |
実行使用メモリ | 9,448 KB |
最終ジャッジ日時 | 2023-09-14 12:56:01 |
合計ジャッジ時間 | 6,043 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
9,440 KB |
testcase_01 | AC | 18 ms
9,284 KB |
testcase_02 | AC | 196 ms
9,344 KB |
testcase_03 | AC | 195 ms
9,328 KB |
testcase_04 | AC | 196 ms
9,440 KB |
testcase_05 | AC | 205 ms
9,324 KB |
testcase_06 | AC | 196 ms
9,320 KB |
testcase_07 | AC | 196 ms
9,280 KB |
testcase_08 | AC | 194 ms
9,448 KB |
testcase_09 | AC | 195 ms
9,196 KB |
testcase_10 | AC | 197 ms
9,368 KB |
testcase_11 | AC | 157 ms
9,280 KB |
testcase_12 | AC | 158 ms
9,432 KB |
testcase_13 | AC | 158 ms
9,268 KB |
testcase_14 | AC | 1 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/modint> using namespace std; //using namespace atcoder; //using mint = modint1000000007; typedef long long ll; #define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I) class comb{ vector<ll> f,fr; ll MOD_; public: //a^(p-1) = 1 (mod p)(p->Prime numbers) //a^(p-2) = a^(-1) ll calc(ll a,ll b,ll p){//a^(b) mod p if(b==0)return 1; ll y = calc(a,b/2,p);y=(y*y)%p; if(b & 1) y = (y * a) % p; return y; } void init(ll n,ll mod){//input max_n MOD_ = mod; f.resize(n+1); fr.resize(n+1); f[0]=fr[0]=1; for(ll i=1;i<n+1;i++){ f[i] = (f[i-1] * i) % mod; } fr[n] = calc(f[n],mod-2,mod); for(ll i=n-1;i>=0;i--){ fr[i] = fr[i+1] * (i+1) % mod; } } ll nCr(ll n,ll r){ if(n<0||r<0||n<r)return 0; return f[n] * fr[r] % MOD_ * fr[n-r] % MOD_; }//nHr = n+r-1Cr }; int main(){ ll N,M; ll MOD = 1000000007; cin >> N >> M; comb co; co.init(2*N+8,MOD); ll ans = 2LL * N * co.nCr(2*N,N) % MOD; FOR(i,0,M){ ll t,x,y; cin >> t >> x >> y; ll sub = co.nCr(x+y,x) * co.nCr((N-x)+(N-y)-1,(N-x)-(t==1)) % MOD; ( ans += MOD - sub ) %= MOD; } cout << ans << endl; }