結果

問題 No.1474 かさまJ
ユーザー KoDKoD
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0