結果

問題 No.1388 Less than K
ユーザー Ryuhei MoriRyuhei Mori
提出日時 2021-03-03 13:16:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 3,000 ms
コード長 1,289 bytes
コンパイル時間 1,019 ms
コンパイル使用メモリ 69,456 KB
実行使用メモリ 6,704 KB
最終ジャッジ日時 2023-07-26 16:33:37
合計ジャッジ時間 6,764 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 3 ms
4,384 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 5 ms
4,620 KB
testcase_18 AC 6 ms
5,172 KB
testcase_19 AC 6 ms
5,468 KB
testcase_20 AC 7 ms
5,576 KB
testcase_21 AC 7 ms
5,824 KB
testcase_22 AC 7 ms
5,724 KB
testcase_23 AC 4 ms
4,380 KB
testcase_24 AC 4 ms
4,508 KB
testcase_25 AC 5 ms
4,828 KB
testcase_26 AC 4 ms
4,900 KB
testcase_27 AC 4 ms
4,736 KB
testcase_28 AC 5 ms
5,004 KB
testcase_29 AC 5 ms
4,952 KB
testcase_30 AC 2 ms
4,384 KB
testcase_31 AC 3 ms
4,376 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 7 ms
6,152 KB
testcase_34 AC 8 ms
5,828 KB
testcase_35 AC 7 ms
5,724 KB
testcase_36 AC 6 ms
5,500 KB
testcase_37 AC 8 ms
6,344 KB
testcase_38 AC 7 ms
5,684 KB
testcase_39 AC 7 ms
5,584 KB
testcase_40 AC 6 ms
5,156 KB
testcase_41 AC 9 ms
6,396 KB
testcase_42 AC 7 ms
5,736 KB
testcase_43 AC 9 ms
6,528 KB
testcase_44 AC 9 ms
6,500 KB
testcase_45 AC 9 ms
6,576 KB
testcase_46 AC 9 ms
6,480 KB
testcase_47 AC 8 ms
6,340 KB
testcase_48 AC 8 ms
6,396 KB
testcase_49 AC 9 ms
6,344 KB
testcase_50 AC 9 ms
6,560 KB
testcase_51 AC 10 ms
6,416 KB
testcase_52 AC 9 ms
6,488 KB
testcase_53 AC 10 ms
6,436 KB
testcase_54 AC 9 ms
6,372 KB
testcase_55 AC 12 ms
6,440 KB
testcase_56 AC 9 ms
6,444 KB
testcase_57 AC 9 ms
6,444 KB
testcase_58 AC 9 ms
6,508 KB
testcase_59 AC 9 ms
6,464 KB
testcase_60 AC 10 ms
6,436 KB
testcase_61 AC 8 ms
6,580 KB
testcase_62 AC 8 ms
6,452 KB
testcase_63 AC 10 ms
6,440 KB
testcase_64 AC 10 ms
6,456 KB
testcase_65 AC 9 ms
6,704 KB
testcase_66 AC 9 ms
6,444 KB
testcase_67 AC 9 ms
6,424 KB
testcase_68 AC 9 ms
6,628 KB
testcase_69 AC 9 ms
6,508 KB
testcase_70 AC 9 ms
6,456 KB
testcase_71 AC 9 ms
6,464 KB
testcase_72 AC 9 ms
6,464 KB
testcase_73 AC 9 ms
6,488 KB
testcase_74 AC 9 ms
6,512 KB
testcase_75 AC 9 ms
6,420 KB
testcase_76 AC 9 ms
6,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>

using u32 = unsigned;
using u64 = unsigned long long;

/*
[x^{0 mod x^{4k+4}} z^{h-w}] (z+1/z+x+1/x)^{h+w}(1-x^{2k+2})
[x^{0 mod x^{4k+4}} z^{h-w}] (z+x)^{h+w} (1 + 1/(zx))^{h+w}(1-x^{2k+2})

\sum_{i=0}^{h+w} binom(h+w, i) * bionm(h+w, i+w-h) * I[h+w-i - (i+w-h) == 0]

0 k * k 0 k *
*/

constexpr u32 mod = 998244353;

u32 fact[400001];
u32 ifact[400001];

u32 binom(u32 n, u32 k){
  return (u64) fact[n] * ifact[k] % mod * ifact[n-k] % mod;
}

u32 pw(u32 a, u32 n){
  u32 r = 1;
  for(; n; n >>= 1){
    if(n&1) r = (u64) r * a % mod;
    a = (u64) a * a % mod;
  }
  return r;
}

u32 inv(u32 a){
  return pw(a, mod-2);
}


int main(){
  u32 h, w, k;
  std::cin >> h >> w >> k;
  h--, w--;
  k /= 2;

  fact[0] = 1;
  for(u32 i = 1; i <= h+w; i++) fact[i] = (u64) i * fact[i-1] % mod;
  ifact[h+w] = inv(fact[h+w]);
  for(u32 i = h+w; i > 0; i--) ifact[i-1] = (u64) i * ifact[i] % mod;

  if(h > w) std::swap(h, w);
  u64 ans = 0;
  for(u32 i = 0; i <= 2*h; i++){
    int j = 2*((int) h - (int) i) % (int) (4*(k+1));
    if(j < 0) j += 4*(k+1);
    if(j != 0 && (u32) j != 2*(k+1)) continue;
    u64 tmp = (u64) binom(h+w, i) * binom(h+w, 2*h-i) % mod;
    if(j == 0) ans += tmp;
    else ans += mod - tmp;
  }

  std::cout << ans % mod << std::endl;

  return 0;
}
0