結果
問題 | No.1520 Zigzag Sum |
ユーザー |
|
提出日時 | 2021-05-28 21:47:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,169 bytes |
コンパイル時間 | 716 ms |
コンパイル使用メモリ | 75,756 KB |
最終ジャッジ日時 | 2025-01-21 19:58:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 |
ソースコード
#include <atcoder/modint> #include <iostream> #include <vector> template <class T> struct Combination { int max_n; std::vector<T> f, invf; explicit Combination(int n) : max_n(n), f(n + 1), invf(n + 1) { f[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = f[i - 1] * i; } invf[max_n] = f[max_n].inv(); for (int i = max_n - 1; i >= 0; --i) { invf[i] = invf[i + 1] * (i + 1); } } T fact(int n) const { return n < 0 ? T(0) : f[n]; } T invfact(int n) const { return n < 0 ? T(0) : invf[n]; } T perm(int a, int b) const { return a < b || b < 0 ? T(0) : f[a] * invf[a - b]; } T binom(int a, int b) const { return a < b || b < 0 ? T(0) : f[a] * invf[a - b] * invf[b]; } }; using namespace std; using mint = atcoder::modint1000000007; const Combination<mint> C(400000); void solve() { int h, w; cin >> h >> w; cout << (C.binom(h + w - 4, h - 2) * (h + w - 3) * 2).val() << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int q; cin >> q; while (q--) solve(); return 0; }