結果

問題 No.1388 Less than K
ユーザー Ryuhei Mori
提出日時 2021-03-03 22:39:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 3,000 ms
コード長 1,266 bytes
コンパイル時間 590 ms
コンパイル使用メモリ 68,572 KB
最終ジャッジ日時 2025-01-19 09:47:59
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

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