結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
|
提出日時 | 2021-07-09 23:46:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 224 ms / 2,000 ms |
コード長 | 1,434 bytes |
コンパイル時間 | 3,872 ms |
コンパイル使用メモリ | 232,532 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-07-01 18:42:55 |
合計ジャッジ時間 | 8,141 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#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; }