結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
|
提出日時 | 2021-07-09 21:50:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 1,534 bytes |
コンパイル時間 | 1,649 ms |
コンパイル使用メモリ | 197,328 KB |
最終ジャッジ日時 | 2025-01-22 21:29:35 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long int; using ld = long double; const ll MAX = 5000000000000000000; const ld PI = 3.14159265358979; const ll MOD = 1000000007;//2024948111; random_device rd; mt19937 mt(rd()); ld dotorad(ld K){return PI * K / 180.0;} ld radtodo(ld K){return K * 180.0 / PI;} const ll COMMAX = 500000; vector<ll> fac(COMMAX + 10000),finv(COMMAX + 10000),inv(COMMAX + 10000); void COMinit(){ inv[1] = 1; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; ll i; for(i = 2;i < COMMAX + 9000;i++){ fac[i] = (fac[i - 1] * i) % MOD; inv[i] = MOD - ((inv[MOD % i] * (MOD / i)) % MOD); finv[i] = (finv[i - 1] * inv[i]) % MOD; } } ll COM(ll n,ll m){ //nCm if (n < m) return 0; if (n < 0 || m < 0) return 0; return (fac[n] * (finv[m] * finv[n - m] % MOD)) % MOD; } int main(){ COMinit(); ll N,M; cin >> N >> M; ll ans = (COM(N * 2,N)) % MOD; ans *= N * 2; ans %= MOD; for(ll i = 0;i < M;i++){ ll t,x,y; cin >> t >> x >> y; if(t == 1){ ll p,q; p = N - (x + 1); q = N - y; ll r = COM(x + y,y) * COM(p + q,q); r %= MOD; ans += MOD - r; ans %= MOD; } else{ ll p,q; p = N - x; q = N - (y + 1); ll r = COM(x + y,y) * COM(p + q,q); r %= MOD; ans += MOD - r; ans %= MOD; } } cout << ans << endl; }