結果

問題 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
コンパイル時間 607 ms
コンパイル使用メモリ 73,300 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-14 06:14:52
合計ジャッジ時間 3,417 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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