結果

問題 No.2527 H and W
ユーザー InTheBloom
提出日時 2023-11-03 22:17:37
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 729 ms / 2,000 ms
コード長 2,461 bytes
コンパイル時間 1,985 ms
コンパイル使用メモリ 207,580 KB
実行使用メモリ 18,304 KB
最終ジャッジ日時 2024-09-25 20:42:23
合計ジャッジ時間 22,397 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std;
void main () {
long H, W, K; readln.read(H, W, K);
solve(H, W, K);
}
void solve (long H, long W, long K) {
const int MOD = 998244353;
/* combination */
const int MAX = 10^^6+1;
long[] fact = new long[](MAX);
long[] factInv = new long[](MAX);
fact[0] = factInv[0] = 1;
for (int i = 1; i < MAX; i++) {
(fact[i] = i*fact[i-1]) %= MOD;
factInv[i] = modInv(fact[i], MOD);
}
long comb (long n_, long k_, const int MOD) {
int n = cast(int) n_, k = cast(int) k_;
if (n < k) return 0;
long res = fact[n];
res *= factInv[k]; res %= MOD;
res *= factInv[n-k]; res %= MOD;
return res;
}
/* n()m = (K-HW-nH)/(W-n)
/* */
if (K == 0) {
/* -> (2^x)21 */
long ans = (modPow(2, H, MOD) + modPow(2, W, MOD))%MOD - 1;
if (ans < 0) ans += MOD;
writeln(ans);
return;
}
long ans = 0;
for (int i = 0; i < W; i++) {
if ((H*W - K - i*H) % (W - i) == 0) {
long choice = (H*W - K - i*H) / (W-i);
if (0 <= choice) ans += (comb(W, i, MOD) * comb(H, choice, MOD)) % MOD; ans %= MOD;
}
}
writeln(ans);
}
void read(T...)(string S, ref T args) {
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
long modPow (long a, long x, const int MOD) {
// assertion
assert(0 <= x);
assert(1 <= MOD);
// normalize
a %= MOD; a += MOD; a %= MOD;
// simple case
if (MOD == 1) {
return 0L;
}
if (x == 0) {
return 1L;
}
if (x == 1) {
return a;
}
// calculate
long res = 1L;
long base = a % MOD;
while (x != 0) {
if ((x&1) != 0) {
res *= base;
res %= MOD;
}
base = base*base; base %= MOD;
x >>= 1;
}
return res;
}
long modInv (long x, const int MOD) {
import std.exception;
enforce(1 <= MOD, format("Line : %s, MOD must be greater than 1. Your input = %s", __LINE__, MOD));
return modPow(x, MOD-2, MOD);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0