結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー | h2929 |
提出日時 | 2021-07-09 23:46:50 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 1,434 bytes |
コンパイル時間 | 3,679 ms |
コンパイル使用メモリ | 231,696 KB |
実行使用メモリ | 6,296 KB |
最終ジャッジ日時 | 2023-09-14 11:13:36 |
合計ジャッジ時間 | 7,948 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
6,008 KB |
testcase_01 | AC | 57 ms
6,212 KB |
testcase_02 | AC | 205 ms
6,004 KB |
testcase_03 | AC | 206 ms
6,180 KB |
testcase_04 | AC | 207 ms
6,296 KB |
testcase_05 | AC | 208 ms
6,188 KB |
testcase_06 | AC | 207 ms
6,000 KB |
testcase_07 | AC | 206 ms
6,140 KB |
testcase_08 | AC | 204 ms
6,052 KB |
testcase_09 | AC | 207 ms
6,136 KB |
testcase_10 | AC | 205 ms
6,132 KB |
testcase_11 | AC | 186 ms
6,256 KB |
testcase_12 | AC | 189 ms
6,192 KB |
testcase_13 | AC | 191 ms
6,036 KB |
testcase_14 | AC | 59 ms
6,008 KB |
testcase_15 | AC | 59 ms
6,112 KB |
testcase_16 | AC | 59 ms
5,996 KB |
testcase_17 | AC | 59 ms
6,260 KB |
testcase_18 | AC | 58 ms
6,000 KB |
testcase_19 | AC | 58 ms
6,280 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define ll long long int #define INF 1000000000000000000 #define N 400000 #define pll pair<ll,ll> using namespace atcoder; using namespace std; using mint = modint1000000007; ostream &operator<<(std::ostream &os, mint p){ os << p.val(); return os; } vector<mint> p(N+1, 0), inv(N+1, 0); void init(){ p[0] = 1; inv[0] = 1; for (ll i = 1; i < N+1; i++){ p[i] = i*p[i-1]; inv[i] = inv[i-1]/i; } } int main(void){ init(); ll n, m; cin >> n >> m; set<pll> rs, cs; mint ans = 2*n*p[2*n]*inv[n]*inv[n]; for (ll i = 0; i < m; i++){ ll c, x, y; cin >> c >> x >> y; mint t = 1; if (c == 1){ t *= p[x+y]*inv[x]*inv[y]; t *= p[2*n-x-y-1]*inv[n-x-1]*inv[n-y]; } else { t *= p[x+y]*inv[x]*inv[y]; t *= p[2*n-x-y-1]*inv[n-x]*inv[n-y-1]; } ans -= t; } cout << ans << endl; /* vector<vector<mint>> dp(n, vector<mint>(n, 0)); vector<vector<mint>> dp2(n, vector<mint>(n, 0)); dp[0][0] = 1; dp2[0][0] = 0; for (ll i = 0; i < n; i++){ for (ll j = 0; j < n; j++){ if (i != n-1){ dp[i+1][j] += dp[i][j]; dp2[i+1][j] += dp2[i][j] + (rs.count(pll(i, j)) ? 0 : dp[i][j]); } if (j != n-1){ dp[i][j+1] += dp[i][j]; dp2[i][j+1] += dp2[i][j] + (cs.count(pll(i, j)) ? 0 : dp[i][j]); } } } cout << dp2[n-1][n-1] << endl; */ return 0; }