結果
問題 | No.1186 長方形の敷き詰め |
ユーザー |
|
提出日時 | 2020-08-22 17:52:16 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 1,694 ms |
コンパイル使用メモリ | 108,576 KB |
実行使用メモリ | 26,804 KB |
最終ジャッジ日時 | 2024-10-15 11:42:25 |
合計ジャッジ時間 | 3,060 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <iostream> #include <utility> #include <tuple> #include <vector> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <algorithm> #include <functional> #include <climits> #include <numeric> #include <queue> #include <cmath> #include <iomanip> #include <array> #include <string> #include <stack> #include <cassert> #include <memory> #include <random> #include <fstream> #include <cfloat> #include <complex> constexpr long long int MOD{ 998244353 }; int main() { int n, m; std::cin >> n >> m; std::vector<long long int> factorial(m + 1, 1), div(m + 1, 1), inv(m + 1, 1); for (auto i = 2; i <= m; ++i) { factorial[i] = i * factorial[i - 1] % MOD; div[i] = (MOD - MOD / i) * div[MOD % i] % MOD; inv[i] = div[i] * inv[i - 1] % MOD; } const auto combination = [&factorial, &inv](const int n, const int r) {return factorial[n] * inv[r] % MOD * inv[n - r] % MOD; }; if (n > m || n == 1) { std::cout << "1\n"; return 0; } else { long long int result{ 0 }; for (auto i = 0; i <= m / n; ++i) { const auto j = m - i * n; const auto pattern = combination(i + j, i); result = (result + pattern) % MOD; } std::cout << result << '\n'; } }