結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
![]() |
提出日時 | 2021-07-09 21:57:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 1,024 bytes |
コンパイル時間 | 2,054 ms |
コンパイル使用メモリ | 198,024 KB |
最終ジャッジ日時 | 2025-01-22 21:40:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using mint = atcoder::modint1000000007; using namespace std; using ll = long long; vector<mint> f0, f1; void init(int n) { f0.resize(n + 1); f0[0] = 1; for (int i = 1; i <= n; i++) { f0[i] = f0[i - 1] * i; } f1.resize(n + 1); f1[n] = f0[n].inv(); for (int i = n; i > 0; i--) { f1[i - 1] = f1[i] * i; } } mint fact(int k) { return f0[k]; } mint comb(int n, int k) { if (n < k || k < 0) return 0; return f0[n] * f1[k] * f1[n - k]; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; init(n * 2); mint r = comb(n * 2, n) * (n * 2); for (int i = 0; i < m; i++) { int t, x, y; cin >> t >> x >> y; if (t == 1) { r -= comb(x + y, y) * comb(n - (x + 1) + n - y, n - y); } else { r -= comb(x + y, y) * comb(n - x + n - (y + 1), n - (y + 1)); } } cout << r.val() << endl; return 0; }