結果

問題 No.1388 Less than K
コンテスト
ユーザー vjudge1
提出日時 2026-04-11 12:16:32
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 10 ms / 3,000 ms
コード長 1,535 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 224 ms
コンパイル使用メモリ 41,856 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2026-04-11 12:16:45
合計ジャッジ時間 3,023 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
class modint
{
public:
	static constexpr int mod = 998244353;
	int val;
	modint(void) : val(0) {}
	modint(int x) : val(x) {}
	modint operator+(const modint& other) const { return modint(val + other.val >= mod ? val + other.val - mod : val + other.val); }
	modint operator-(const modint& other) const { return modint(val < other.val ? val - other.val + mod : val - other.val); }
	modint operator*(const modint& other) const { return modint(val * (long long)(other.val) % mod); }
};
modint frac[400005], inv[400005];
int n, m, k;
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	k >>= 1;
	frac[0] = 1;
	for (int i = 1; i <= n + m; ++i)
		frac[i] = frac[i - 1] * i;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= n + m; ++i)
		inv[i] = inv[modint::mod % i] * (modint::mod - modint::mod / i);
	for (int i = 2; i <= n + m; ++i)
		inv[i] = inv[i - 1] * inv[i];
	modint ans = frac[n + m - 2] * inv[n - 1] * inv[m - 1];
	ans = ans * ans;
	// modint ans;
	// for (int i = 0; i <= n + m - 2; i += 2)
		// ans = ans + frac[n + m - 2] * inv[i >> 1] * inv[i >> 1] * inv[(n + m - 2 - i) >> 1] * inv[(n + m - 2 - i) >> 1];
	int a = n - m;
	if (a < 0)
		a = -a;
	for (int i = 1; i * (k + k + 2) + a <= n + m - 2; ++i)
	{
		int b = i * (k + k + 2);
		modint delta = frac[n + m - 2] * inv[(n + m - 2 + a + b) >> 1] * inv[(n + m - 2 - a - b) >> 1] *
			frac[n + m - 2] * inv[(n + m - 2 + a - b) >> 1] * inv[(n + m - 2 - a + b) >> 1] * 2;
		if (i & 1)
			ans = ans - delta;
		else
			ans = ans + delta;
	}
	printf("%d\n", ans.val);
	return 0;
}
0