結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー | Joe75792433 |
提出日時 | 2021-07-09 21:50:46 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 2,693 bytes |
コンパイル時間 | 5,259 ms |
コンパイル使用メモリ | 259,868 KB |
実行使用メモリ | 28,316 KB |
最終ジャッジ日時 | 2023-09-14 08:34:15 |
合計ジャッジ時間 | 7,471 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
28,092 KB |
testcase_01 | AC | 56 ms
28,088 KB |
testcase_02 | AC | 112 ms
28,044 KB |
testcase_03 | AC | 110 ms
28,092 KB |
testcase_04 | AC | 109 ms
28,032 KB |
testcase_05 | AC | 113 ms
28,148 KB |
testcase_06 | AC | 109 ms
28,024 KB |
testcase_07 | AC | 113 ms
28,024 KB |
testcase_08 | AC | 114 ms
28,092 KB |
testcase_09 | AC | 110 ms
28,024 KB |
testcase_10 | AC | 109 ms
28,040 KB |
testcase_11 | AC | 97 ms
28,028 KB |
testcase_12 | AC | 100 ms
28,092 KB |
testcase_13 | AC | 99 ms
28,088 KB |
testcase_14 | AC | 53 ms
28,152 KB |
testcase_15 | AC | 50 ms
28,040 KB |
testcase_16 | AC | 53 ms
28,044 KB |
testcase_17 | AC | 52 ms
28,036 KB |
testcase_18 | AC | 56 ms
28,088 KB |
testcase_19 | AC | 54 ms
28,316 KB |
ソースコード
#ifdef _DEBUG #include <atcoder/all.h> #define debug(x) std::cout << #x << ": " << x << std::endl #else #include <bits/stdc++.h> #include <atcoder/all> //#pragma GCC target("arch=skylake-avx512") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define debug(x) #endif using namespace std; using namespace atcoder; using ll = long long; #define rep(...) _overloadrep(__VA_ARGS__, _rep4, _rep3, _rep2)(__VA_ARGS__) #define _overloadrep(_1, _2, _3, _4, _repn, ...) _repn #define _rep2(i, n) _rep4(i, 0, n, 1) #define _rep3(i, a, b) _rep4(i, a, b, 1) #define _rep4(i, a, b, s) for (auto i = (a); i < (b); i += (s)) #define repr(i, a, b) for (auto i = (b)-1; i >= (a); --i) #define all(x) (x).begin(), (x).end() #define siz(x) int((x).size()) template<class T1, class T2> inline bool chmax(T1 &a, const T2 &b) { if (a < b) { a = b; return true; } return false; } template<class T1, class T2> inline bool chmin(T1 &a, const T2 &b) { if (a > b) { a = b; return true; } return false; } constexpr char enl = '\n'; constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; constexpr long double eps = 1e-10; constexpr int INF = 1010000000; // 1e9 constexpr ll llINF = 3010000000000000000LL; // 3e18 constexpr ll MOD = 1000000007LL; //constexpr ll MOD = 998244353LL; using mint = static_modint<MOD>; constexpr int MAX_COM = 2'100'000; // 2e6 mint COM(int n, int k) { // 二項係数nCkのMODを求める // 前計算O(n),クエリO(1) // 制約: MODは素数, MOD > n static bool init = true; static mint fac[MAX_COM], finv[MAX_COM], inv[MAX_COM]; // テーブルを作る前処理 if (init) { assert(mint::mod() > MAX_COM); init = false; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX_COM; i++) { fac[i] = fac[i - 1] * i; inv[i] = -inv[mint::mod() % i] * (mint::mod() / i); finv[i] = finv[i - 1] * inv[i]; } } // 二項係数計算 if (n < k) return 0; if (n < 0 || k < 0) return 0; assert(n < MAX_COM); return fac[n] * finv[k] * finv[n - k]; } void Main([[maybe_unused]] int testcase_i) { int n, m; cin >> n >> m; mint ans = 2*n * COM(2*n, n); rep(i, m) { int t, x, y; cin >> t >> x >> y; if (t == 1) ans -= COM(x+y, x) * COM(2*n-x-y-1, n-y); else ans -= COM(x+y, x) * COM(2*n-x-y-1, n-x); } cout << ans.val() << enl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int t = 1; //cin >> t; rep(i, t) Main(i); }