提出 #41103973

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

bool init = false;
mint fact[1000006];

// nCr : n 個のマスから r 個選ぶ選び方
mint comb(int n, int r){
  return fact[n] / fact[n - r] / fact[r];
}

int H, W, K;

map<pair<int, int>, mint> mp;

vector<mint> buf;

mint f(int h, int w){
  if (h * w < K || h < 0 || w < 0) return 0;
  return mint(buf[h*w]);
}

mint g(int h, int w){
  mint ans =
    f(h, w)
    - (f(h-1, w) + f(h-1, w) + f(h, w-1) + f(h, w-1)
       - f(h-1, w-1) - f(h-2, w) - f(h-1,w-1) - f(h-1, w-1) - f(h, w-2) - f(h-1, w-1)
       + f(h-1, w-2) + f(h-2, w-1) + f(h-1, w-2) + f(h-2, w-1)
       - f(h-2, w-2)
       );
  return ans;
}

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  cin >> H >> W >> K;

  // Init tables
  fact[0] = 1;
  for (int i = 1; i <= 1000000; i++){
    fact[i] = fact[i - 1] * i;
  }
  buf.resize(H*W+1);
  for (int i = K; i <= H*W; i++){
    buf[i] = comb(i, K);
  }
  
  mint ans = 0;

  for (int y = 1; y <= H; y++){
    ll ny = H - y + 1;
    for (int x = 1; x <= W; x++){
      ll nx = W - x + 1;
      int area = y * x;
      if (area >= K){
	ans += ny * nx * area * g(y, x) / f(H, W);
      }
    }
  }

  cout << ans.val() << endl;
  return 0;
}

提出情報

ジャッジ結果