結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
![]() |
提出日時 | 2021-07-09 22:07:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 2,488 bytes |
コンパイル時間 | 5,496 ms |
コンパイル使用メモリ | 200,180 KB |
最終ジャッジ日時 | 2025-01-22 21:53:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:103:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 103 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:108:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 108 | scanf("%d%d%d", &t, &x, &y); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> #define For(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rFor(i, a, b) for (int i = (int)(a)-1; i >= (int)(b); --i) #define rep(i, n) For(i, 0, (n)) #define rrep(i, n) rFor(i, (n), 0) #define fi first #define se second using namespace std; typedef long long lint; typedef unsigned long long ulint; typedef pair<int, int> pii; typedef pair<lint, lint> pll; template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template <class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } template <class T> T div_floor(T a, T b) { if (b < 0) a *= -1, b *= -1; return a >= 0 ? a / b : (a + 1) / b - 1; } template <class T> T div_ceil(T a, T b) { if (b < 0) a *= -1, b *= -1; return a > 0 ? (a - 1) / b + 1 : a / b; } template <typename T> struct coord_comp { vector<T> v; bool sorted = false; coord_comp() {} int size() { return v.size(); } void add(T x) { v.push_back(x); } void build() { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); sorted = true; } int get_idx(T x) { assert(sorted); return lower_bound(v.begin(), v.end(), x) - v.begin(); } T &operator[](int i) { return v[i]; } }; constexpr lint mod = 1000000007; constexpr lint INF = mod * mod; constexpr int MAX = 200010; using namespace atcoder; using mint = modint1000000007; vector<mint> fact; vector<mint> revfact; void setfact(int n) { fact.resize(n + 1); revfact.resize(n + 1); fact[0] = 1; rep(i, n) fact[i + 1] = fact[i] * mint(i + 1); revfact[n] = fact[n].inv(); for (int i = n - 1; i >= 0; i--) revfact[i] = revfact[i + 1] * mint(i + 1); } mint getC(int n, int r) { if (n < r || r < 0) return 0; return fact[n] * revfact[r] * revfact[n - r]; } int dx[2] = {1, 0}; int dy[2] = {0, 1}; int main() { int n, m; scanf("%d%d", &n, &m); setfact(n * 2); vector<pair<int, pii>> v; rep(i, m) { int t, x, y; scanf("%d%d%d", &t, &x, &y); --t; v.push_back({t, {x, y}}); } mint ans = getC(n * 2, n) * (n * 2); for (auto [t, p] : v) { auto [x, y] = p; int nx = x + dx[t], ny = y + dy[t]; ans -= getC(x + y, x) * getC(n * 2 - nx - ny, n - nx); } printf("%u\n", ans.val()); }