結果

問題 No.1388 Less than K
ユーザー Ryuhei MoriRyuhei Mori
提出日時 2021-03-03 22:39:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 9 ms / 3,000 ms
コード長 1,266 bytes
コンパイル時間 660 ms
コンパイル使用メモリ 70,376 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-03 13:45:58
合計ジャッジ時間 3,066 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 3 ms
6,820 KB
testcase_17 AC 3 ms
6,816 KB
testcase_18 AC 4 ms
6,816 KB
testcase_19 AC 5 ms
6,820 KB
testcase_20 AC 5 ms
6,820 KB
testcase_21 AC 5 ms
6,816 KB
testcase_22 AC 6 ms
6,820 KB
testcase_23 AC 3 ms
6,820 KB
testcase_24 AC 4 ms
6,816 KB
testcase_25 AC 3 ms
6,816 KB
testcase_26 AC 5 ms
6,820 KB
testcase_27 AC 4 ms
6,816 KB
testcase_28 AC 4 ms
6,820 KB
testcase_29 AC 3 ms
6,820 KB
testcase_30 AC 2 ms
6,820 KB
testcase_31 AC 3 ms
6,820 KB
testcase_32 AC 2 ms
6,816 KB
testcase_33 AC 6 ms
6,820 KB
testcase_34 AC 5 ms
6,816 KB
testcase_35 AC 5 ms
6,816 KB
testcase_36 AC 5 ms
6,820 KB
testcase_37 AC 6 ms
6,816 KB
testcase_38 AC 5 ms
6,816 KB
testcase_39 AC 5 ms
6,820 KB
testcase_40 AC 5 ms
6,816 KB
testcase_41 AC 6 ms
6,816 KB
testcase_42 AC 5 ms
6,820 KB
testcase_43 AC 7 ms
6,820 KB
testcase_44 AC 6 ms
6,816 KB
testcase_45 AC 7 ms
6,816 KB
testcase_46 AC 7 ms
6,816 KB
testcase_47 AC 6 ms
6,820 KB
testcase_48 AC 5 ms
6,816 KB
testcase_49 AC 7 ms
6,816 KB
testcase_50 AC 5 ms
6,816 KB
testcase_51 AC 6 ms
6,816 KB
testcase_52 AC 5 ms
6,820 KB
testcase_53 AC 6 ms
6,816 KB
testcase_54 AC 6 ms
6,816 KB
testcase_55 AC 9 ms
6,820 KB
testcase_56 AC 6 ms
6,816 KB
testcase_57 AC 6 ms
6,816 KB
testcase_58 AC 6 ms
6,816 KB
testcase_59 AC 7 ms
6,820 KB
testcase_60 AC 6 ms
6,816 KB
testcase_61 AC 6 ms
6,820 KB
testcase_62 AC 6 ms
6,820 KB
testcase_63 AC 6 ms
6,816 KB
testcase_64 AC 6 ms
6,820 KB
testcase_65 AC 7 ms
6,820 KB
testcase_66 AC 7 ms
6,816 KB
testcase_67 AC 6 ms
6,816 KB
testcase_68 AC 6 ms
6,820 KB
testcase_69 AC 6 ms
6,816 KB
testcase_70 AC 7 ms
6,816 KB
testcase_71 AC 6 ms
6,820 KB
testcase_72 AC 7 ms
6,820 KB
testcase_73 AC 6 ms
6,820 KB
testcase_74 AC 6 ms
6,820 KB
testcase_75 AC 6 ms
6,820 KB
testcase_76 AC 5 ms
6,816 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;
  u32 e = h % (2*(k+1));
  for(u32 i = e; i <= 2*h; i+=2*(k+1)){
    ans += (u64) binom(h+w, i) * binom(h+w, 2*h-i) % mod;
  }
  for(u32 i = (e + (k+1)) % (2*(k+1)); i <= 2*h; i+=2*(k+1)){
    ans += mod - (u64) binom(h+w, i) * binom(h+w, 2*h-i) % mod;
  }

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

  return 0;
}
0