結果

問題 No.1388 Less than K
ユーザー Ryuhei Mori
提出日時 2021-03-03 13:16:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 3,000 ms
コード長 1,289 bytes
コンパイル時間 538 ms
コンパイル使用メモリ 68,096 KB
最終ジャッジ日時 2025-01-19 09:44:20
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
  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