結果
問題 | No.2475 Distance Permutation |
ユーザー |
![]() |
提出日時 | 2023-09-08 18:54:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,068 bytes |
コンパイル時間 | 10,520 ms |
コンパイル使用メモリ | 324,916 KB |
実行使用メモリ | 45,856 KB |
最終ジャッジ日時 | 2024-06-26 17:59:34 |
合計ジャッジ時間 | 13,740 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | RE * 25 |
ソースコード
#include <atcoder/all> #include <cmath> #include <cstdint> #include <iostream> #include <map> #include "testlib.h" using namespace std; using namespace atcoder; using mint = modint998244353; using i32 = int32_t; #define REP(i, s, t) for (i32 i = (s); i < (t); ++i) #define PER(i, s, t) for (i32 i = (t)-1; i >= (s); --i) vector<mint> fact, ifact, inv; const i32 m = 100000; void init(void) { fact.resize(m + 1, 1); ifact.resize(m + 1, 1); inv.resize(m + 1, 1); REP(i, 1, m + 1) fact.at(i) = i * fact.at(i - 1); ifact.at(m) = fact.at(m).inv(); PER(i, 1, m) { inv.at(i + 1) = ifact.at(i + 1) * fact.at(i); ifact.at(i) = ifact.at(i + 1) * (i + 1); } } int main(int argc, char **argv) { cin.tie(nullptr); ios::sync_with_stdio(false); registerValidation(argc, argv); init(); const i32 k = inf.readInt(1, m); inf.readSpace(); const i32 q = inf.readInt(1, m); inf.readEoln(); vector<mint> dp(m + 1); dp[0] = 1; mint sum = 1; REP(i, 1, m + 1) { if (i > k) sum -= dp[i - k - 1]; dp[i] = sum * inv[i]; sum += dp[i]; } const i32 batch = 2000; vector<vector<mint>> memo; REP(i, 0, m / batch) { vector<mint> a(dp.begin(), dp.begin() + i * batch); vector<mint> b = convolution(a, dp); if (b.empty()) { b.resize(m + 1); } memo.emplace_back(b); } auto calc = [&](const i32 n, const i32 k) -> mint { assert(k <= n); if (k < 0) return 0; const i32 p = k / batch; mint res = memo[p][n]; REP(i, p * batch, k + 1) res += dp[i] * dp[n - i]; return res; }; REP(i, 0, q) { const i32 n = inf.readInt(1, m); inf.readSpace(); const i32 l = inf.readInt(1, n); inf.readSpace(); const i32 r = inf.readInt(l, n); inf.readEoln(); mint ans = calc(n - 1, r - 1) - calc(n - 1, l - 2); ans *= fact[n - 1]; cout << ans.val() << "\n"; } inf.readEof(); return 0; }