結果
問題 | No.1474 かさまJ |
ユーザー | KoD |
提出日時 | 2021-04-09 22:06:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,500 ms |
コード長 | 7,590 bytes |
コンパイル時間 | 2,166 ms |
コンパイル使用メモリ | 211,780 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-06-25 05:35:02 |
合計ジャッジ時間 | 3,420 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 31 ms
7,296 KB |
testcase_06 | AC | 12 ms
6,944 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 45 ms
7,424 KB |
testcase_10 | AC | 4 ms
6,944 KB |
testcase_11 | AC | 4 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 69 ms
8,064 KB |
testcase_14 | AC | 17 ms
6,940 KB |
testcase_15 | AC | 11 ms
6,940 KB |
testcase_16 | AC | 5 ms
6,940 KB |
testcase_17 | AC | 23 ms
6,940 KB |
testcase_18 | AC | 96 ms
9,216 KB |
testcase_19 | AC | 113 ms
9,728 KB |
testcase_20 | AC | 119 ms
9,856 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> andstd::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;}