提出 #31121531

---

ソースコード 拡げる

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

struct Binomial {
  vector<mint> fac, invfac, inv;
  Binomial(int n) : fac(n + 1), invfac(n + 1), inv(n + 1) {
    fac[0] = invfac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
    invfac[n] = fac[n].inv();
    for (int i = n - 1; i >= 0; i--) {
      invfac[i] = invfac[i + 1] * (i + 1);
      inv[i + 1] = invfac[i + 1] * fac[i];
    }
  }
  mint operator()(int n, int r) {
    if (n < 0 || r < 0 || n < r) return 0;
    return fac[n] * invfac[n - r] * invfac[r];
  }
} C{100100};

mint calc1(long long H, long long W) {
  mint res = 0;
  for (int i = 0; i <= H; i++) {
    if (i % W == (H - i) % W) res += C(H, i);
  }
  return res * W;
}

mint calc2(long long H, long long W) {
  auto mul = [&](vector<mint>& a, vector<mint>& b) {
    auto c = atcoder::convolution(a, b);
    for (int i = W; i < (int)c.size(); i++) c[i % W] += c[i];
    c.resize(W);
    return c;
  };
  vector<mint> base(W), res(W);
  base[1] += 1, base[W - 1] += 1;
  res[0] = 1;
  while (H) {
    if (H & 1) res = mul(res, base);
    base = mul(base, base);
    H >>= 1;
  }
  return res[0] * W;
}

mint solve(long long H, long long W) {
  if (H % 2 == 0 and W % 2 == 0) return 2;
  if (H < W) swap(H, W);
  if (W % 2 == 0) swap(H, W);
  if (H <= 100000) return calc1(H, W);
  return calc2(H, W);
}

int main() {
  long long H, W;
  cin >> H >> W;
  cout << solve(H, W).val() << endl;
}

提出情報

ジャッジ結果