結果
問題 | No.1520 Zigzag Sum |
ユーザー |
![]() |
提出日時 | 2021-05-28 22:09:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 2,179 bytes |
コンパイル時間 | 981 ms |
コンパイル使用メモリ | 93,560 KB |
実行使用メモリ | 9,768 KB |
最終ジャッジ日時 | 2024-11-07 09:38:30 |
合計ジャッジ時間 | 2,431 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 |
ソースコード
#include <iostream>#include <string>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <cassert>#include <numeric>#include <functional>#include <ctime>#pragma warning(disable:4996)//#define ATCODER#ifdef ATCODER#include <atcoder/all>#endiftypedef long long ll;typedef unsigned long long ull;#define LINF 9223300000000000000#define LINF2 1223300000000000000#define LINF3 1000000000000#define INF 2140000000const long long MOD = 1000000007;//const long long MOD = 998244353;using namespace std;#ifdef ATCODERusing namespace atcoder;#endifconst int max_comb = 410000;vector<ll> fac(max_comb + 1); //n! (mod M)vector<ll> ifac(max_comb + 1); //k!^(-1) (mod M)ll mpow(ll x, ll n) { //x^n(mod M)ll ans = 1;while (n != 0) {if (n & 1) ans = ans * x % MOD;x = x * x % MOD;n = n >> 1;}return ans;}ll minv(ll x) {return mpow(x, MOD - 2);}ll comb(int a, int b) { // C(a,b) = a! * b!^(-1) * (a-b)^(-1)if (a == 0 && b == 0)return 1;if (a < b || a < 0)return 0;ll tmp = ifac[a - b] * ifac[b] % MOD;return tmp * fac[a] % MOD;}ll perm(int a, int b) { // P(a,b) = a! * (a-b)!^(-1)if (b == 0)return 1;if (a < b || a < 0)return 0;ll tmp = ifac[a - b] % MOD;return tmp * fac[a] % MOD;}void pre_comb(){fac[0] = 1;ifac[0] = 1;for (int i = 0; i < max_comb; i++) {fac[i + 1] = fac[i] * (i + 1) % MOD; // n!(mod M)ifac[i + 1] = ifac[i] * minv(i + 1) % MOD; // k!^(-1) (mod M)}return;}void solve(){int h, w;scanf("%d%d", &h, &w);if (h == 1 || w == 1) {printf("0\n");}else {ll ans = (h + w - 3) * 2 % MOD;ans = ans * comb(h + w - 4, h - 2) % MOD;printf("%lld\n", ans);}return;}int main(){#if 0solve();#elsepre_comb();int T, t;scanf("%d", &T);for (t = 0; t < T; t++) {//printf("Case #%d: ", t + 1);solve();}#endifreturn 0;}