結果
問題 | No.1474 かさまJ |
ユーザー | KoD |
提出日時 | 2021-04-09 22:06:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,500 ms |
コード長 | 7,590 bytes |
コンパイル時間 | 2,383 ms |
コンパイル使用メモリ | 209,492 KB |
実行使用メモリ | 9,764 KB |
最終ジャッジ日時 | 2023-09-07 11:24:47 |
合計ジャッジ時間 | 4,013 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 32 ms
7,388 KB |
testcase_06 | AC | 13 ms
4,380 KB |
testcase_07 | AC | 4 ms
4,380 KB |
testcase_08 | AC | 3 ms
4,376 KB |
testcase_09 | AC | 45 ms
7,156 KB |
testcase_10 | AC | 4 ms
4,376 KB |
testcase_11 | AC | 3 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,380 KB |
testcase_13 | AC | 76 ms
7,692 KB |
testcase_14 | AC | 19 ms
4,712 KB |
testcase_15 | AC | 13 ms
4,376 KB |
testcase_16 | AC | 5 ms
4,376 KB |
testcase_17 | AC | 24 ms
6,180 KB |
testcase_18 | AC | 110 ms
9,200 KB |
testcase_19 | AC | 129 ms
9,728 KB |
testcase_20 | AC | 135 ms
9,764 KB |
ソースコード
#include <bits/stdc++.h> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template <class T> constexpr T rem_euclid(T value, const T& mod) { return (value %= mod) >= 0 ? value : value + mod; } template <u32 MOD, std::enable_if_t<((u32)1 <= MOD and MOD <= ((u32)1 << 31))>* = nullptr> class StaticModint { using Mint = StaticModint; static inline constexpr u32 PHI = [] { u32 x = MOD, ret = MOD; for (u32 i = 2; i * i <= x; ++i) { if (x % i == 0) { ret /= i; ret *= i - 1; while (x % i == 0) x /= i; } } if (x > 1) { ret /= x; ret *= x - 1; } return ret; }(); u32 v; public: static constexpr u32 mod() noexcept { return MOD; } template <class T, std::enable_if_t<std::is_signed_v<T> and std::is_integral_v<T>>* = nullptr> static constexpr T normalize(const T x) noexcept { return rem_euclid<std::common_type_t<T, i64>>(x, MOD); } template <class T, std::enable_if_t<std::is_unsigned_v<T> and std::is_integral_v<T>>* = nullptr> static constexpr T normalize(const T x) noexcept { return x % MOD; } constexpr StaticModint() noexcept : v(0) {} template <class T> explicit constexpr StaticModint(const T x) noexcept : v(normalize(x)) {} template <class T> static constexpr Mint raw(const T x) noexcept { Mint ret; ret.v = x; return ret; } constexpr u32 get() const noexcept { return v; } constexpr Mint neg() const noexcept { return raw(v == 0 ? 0 : MOD - v); } constexpr Mint inv() const noexcept { return pow(PHI - 1); } constexpr Mint pow(u64 exp) const noexcept { Mint ret(1), mult(*this); for (; exp > 0; exp >>= 1) { if (exp & 1) ret *= mult; mult *= mult; } return ret; } constexpr Mint operator-() const noexcept { return neg(); } constexpr Mint operator~() const noexcept { return inv(); } constexpr Mint operator+(const Mint& rhs) const noexcept { return Mint(*this) += rhs; } constexpr Mint& operator+=(const Mint& rhs) noexcept { if ((v += rhs.v) >= MOD) v -= MOD; return *this; } constexpr Mint operator-(const Mint& rhs) const noexcept { return Mint(*this) -= rhs; } constexpr Mint& operator-=(const Mint& rhs) noexcept { if (v < rhs.v) v += MOD; v -= rhs.v; return *this; } constexpr Mint operator*(const Mint& rhs) const noexcept { return Mint(*this) *= rhs; } constexpr Mint& operator*=(const Mint& rhs) noexcept { v = (u64)v * rhs.v % MOD; return *this; } constexpr Mint operator/(const Mint& rhs) const noexcept { return Mint(*this) /= rhs; } constexpr Mint& operator/=(const Mint& rhs) noexcept { return *this *= rhs.inv(); } constexpr bool operator==(const Mint& rhs) const noexcept { return v == rhs.v; } constexpr bool operator!=(const Mint& rhs) const noexcept { return v != rhs.v; } friend std::ostream& operator<<(std::ostream& stream, const Mint& rhs) { return stream << rhs.v; } }; constexpr u64 ceil_log2(const u64 x) { u64 e = 0; while (((u64)1 << e) < x) ++e; return e; } template <class F> class AutoRealloc { using R = typename decltype(std::declval<F>()((usize)0))::value_type; F func; std::vector<R> data; public: template <class G> explicit AutoRealloc(G&& g) : func(std::forward<G>(g)), data() {} void reserve(const usize size) { if (data.size() < size) { const usize pow2 = ((usize)1 << ceil_log2(size)); data = func(pow2); } } R operator[](const usize i) { reserve(i + 1); return data[i]; } }; template <class G> explicit AutoRealloc(G&&) -> AutoRealloc<std::decay_t<G>>; template <class M> struct ModintUtil { static inline auto fact = AutoRealloc([](const usize n) { std::vector<M> ret(n); ret[0] = M(1); for (const usize i : rep(1, n)) { ret[i] = ret[i - 1] * M(i); } return ret; }); static inline auto inv = AutoRealloc([](const usize n) { std::vector<M> ret(n); if (n == 1) return ret; ret[1] = M(1); for (const usize i : rep(2, n)) { ret[i] = -M(M::mod() / i) * ret[M::mod() % i]; } return ret; }); static inline auto inv_fact = AutoRealloc([](const usize n) { std::vector<M> ret(n); ret[0] = M(1); for (const usize i : rep(1, n)) { ret[i] = ret[i - 1] * inv[i]; } return ret; }); static M binom(const usize n, const usize k) { assert(k <= n); return fact[n] * inv_fact[n - k] * inv_fact[k]; } static M factpow(const usize n, const usize k) { assert(k <= n); return fact[n] * inv_fact[n - k]; } static M homo(const usize n, const usize k) { if (n == 0 and k == 0) return M(1); return binom(n + k - 1, k); } }; template <class T> using Vec = std::vector<T>; using Fp = StaticModint<1000000007>; using FpUtil = ModintUtil<Fp>; void F_main() { usize N, Mp, Mq, L; std::cin >> N >> Mp >> Mq >> L; Vec<usize> S(N); for (auto& x : S) { std::cin >> x; } Vec<Vec<Fp>> dp(1, Vec<Fp>(Mq + 1)); dp[0][0] = Fp(1); for (const auto x : S) { Vec<Vec<Fp>> next(dp.size() + 1, Vec<Fp>(Mq + 1)); for (const auto i : rep(0, dp.size())) { Vec<Fp> sum(Mq + 2); for (const auto j : rep(0, Mq + 1)) { if (dp[i][j] == Fp(0)) { continue; } next[i][j] += dp[i][j]; sum[j + 1] += dp[i][j]; sum[std::min(Mq + 1, j + x + 1)] -= dp[i][j]; } for (const auto j : rep(0, Mq + 1)) { sum[j + 1] += sum[j]; next[i + 1][j] += sum[j]; } } dp = std::move(next); } Fp ans; for (const auto i : rep(0, dp.size())) { for (const auto j : rep(0, Mq + 1)) { if (dp[i][j] == Fp(0)) { continue; } const auto need = L * i - j; if (Mp < need) { continue; } ans += dp[i][j] * FpUtil::homo(N, Mp - need); } } std::cout << ans << '\n'; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); F_main(); return 0; }