結果
問題 |
No.1191 数え上げを愛したい(数列編)
|
ユーザー |
![]() |
提出日時 | 2021-03-05 18:43:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 499 ms / 2,000 ms |
コード長 | 1,393 bytes |
コンパイル時間 | 876 ms |
コンパイル使用メモリ | 84,444 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-10-06 20:41:15 |
合計ジャッジ時間 | 15,046 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <iostream> #include <map> #include <set> #include <queue> #include <cmath> #include <vector> #include <string> #include <algorithm> #include <functional> using namespace std; #pragma warning (disable: 4996) long long modpow(long long a, long long b, long long m) { long long p = 1, q = a; for (int i = 0; i < 63; i++) { if ((b / (1LL << i)) % 2LL == 1) { p *= q; p %= m; } q *= q; q %= m; } return p; } long long Div(long long a, long long b, long long m) { return (a * modpow(b, m - 2, m)) % m; } long long mod = 998244353; long long fact[1 << 19]; long long factinv[1 << 19]; // 入力 long long N, M, A, B; long long Answer = 0; long long ncr(long long n, long long r) { if (r < 0 || n < r) return 0; return (fact[n] * factinv[r] % mod) * factinv[n - r] % mod; } int main() { // Step #1. 入力・調整 cin >> N >> M >> A >> B; M -= (N - 1) * (A - 1); B -= (N - 1) * (A - 1); // Step #2. 階乗の計算 fact[0] = 1; for (int i = 1; i <= 300000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod; for (int i = 0; i <= 300000; i++) factinv[i] = Div(1, fact[i], mod); // Step #3. 動的計画法 for (int i = 1; i <= M; i++) { long long kosuu = min(B + 1LL, M - i + 1LL); long long ret = ncr(kosuu - 1, N - 1); Answer += ret; Answer %= mod; } // Step #4. 出力 long long FinalAns = Answer * fact[N] % mod; cout << FinalAns << endl; return 0; }