結果
| 問題 | No.1474 かさまＪ |
| コンテスト | |
| ユーザー |
👑  希丝缇娜菲贝尔
|
| 提出日時 | 2026-09-14 19:39:06 |
| 言語 | C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 364 ms / 2,500 ms |
| + 58µs | |
| コード長 | 5,827 bytes |
| 記録 | |
| コンパイル時間 | 4,169 ms |
| コンパイル使用メモリ | 293,424 KB |
| 実行使用メモリ | 32,288 KB |
| 最終ジャッジ日時 | 2026-09-14 19:39:14 |
| 合計ジャッジ時間 | 8,049 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 17 |
ソースコード
#ifdef MAIN
bool __multi__ = 0;
namespace XK {
// X_i + Y_i >= L => Z_i = X_i - (L - Y_i) >= 0 最低要求
// Rem = Mp - kL + Q
// {Mp - kL + Q + N - 1} C {N - 1}
const ll mod = 1e9 + 7;
struct mm {
ll x;
mm(ll x_ = 0) : x(x_ % mod) {
if(x < 0) x += mod;
}
friend mm operator+(mm a, mm b) { return a.x + b.x; }
friend mm operator-(mm a, mm b) { return a.x - b.x; }
friend mm operator*(mm a, mm b) { return a.x * b.x; }
friend mm operator/(mm a, mm b) { return a * b.inv(); }
friend mm& operator+=(mm& a, mm b) { return a = a.x + b.x; }
friend mm& operator-=(mm& a, mm b) { return a = a.x - b.x; }
friend mm& operator*=(mm& a, mm b) { return a = a.x * b.x; }
friend mm& operator/=(mm& a, mm b) { return a = a * b.inv(); }
mm inv() const { return pow(mod - 2); }
mm pow(ll b) const {
mm a = *this, c = 1;
while(b) {
if(b & 1) c *= a;
a *= a;
b >>= 1;
}
return c;
}
};
struct Comb {
private:
vector<mm> fact;
vector<mm> invf;
public:
Comb(int _n) {
fact.resize(_n + 1);
invf.resize(_n + 1);
fact[0] = 1;
Rep(i, 1, _n + 1) fact[i] = fact[i - 1] * i;
invf[_n] = fact[_n].inv();
for(int i = _n; i > 0; i --) invf[i - 1] = invf[i] * i;
}
mm C(int n, int k) {
if(k < 0 || k > n) return 0;
return fact[n] * invf[k] * invf[n - k];
}
};
void solve() {
Comb comb(1e6);
int N, Mp, Mq, L; in(N, Mp, Mq, L);
V<int> S(N); in(S);
V<V<mm>> f(N + 1, V<mm>(Mq + 1, 0));
f[0][0] = 1;
rep(i, N) {
V<V<mm>> nf(N + 1, V<mm>(Mq + 1, 0));
rep(j, i + 1) {
rep(k, Mq + 1)
nf[j][k] += f[j][k];
mm pre[Mq + 1]{0};
rep(k, Mq + 1) {
pre[k] = f[j][k];
if(k) pre[k] += pre[k - 1];
}
rep(k, Mq + 1) {
int r = k - 1;
int l = max<int>(0, k - S[i]);
if(r >= l) {
nf[j + 1][k] += pre[r] - (l == 0 ? 0 : pre[l - 1]);
}
}
}
swap(f, nf);
}
mm ans = 0;
rep(k, N + 1) rep(q, Mq + 1) {
ans += f[k][q] * comb.C(Mp - k * L + q + N - 1, N - 1);
}
out(ans.x);
}
};
signed main() {ios::sync_with_stdio(0);cin.tie(0);fixed(cout).precision(12);int t = 1;if(__multi__) cin >> t;while(t --) XK::solve();}
#else
#include "cassert"
#include "cmath"
#include "cstdint"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "algorithm"
#include "bitset"
#include "chrono"
#include "complex"
#include "deque"
#include "functional"
#include "iostream"
#include "limits"
#include "map"
#include "numeric"
#include "queue"
#include "random"
#include "set"
#include "sstream"
#include "string"
#include "unordered_map"
#include "unordered_set"
#include "utility"
#include "vector"
#include "array"
using namespace std;
#define int long long
using ll = long long;
using ull = unsigned long long;
const ll INF = 1ll << 60;
const ll LINF = 0x1fffffffffffffff;
const ll MINF = 0x7fffffffffff;
template <class A, class B> bool chmax(A& l, const B& r){ return r > l ? l = r, 1 : 0; }
template <class A, class B> bool chmin(A& l, const B& r){ return r < l ? l = r, 1 : 0; }
#define sz(x) ssize(x)
#define rep(i, a) for(ll i = 0; i < (a); i ++)
#define Rep(i, a, b) for(ll i = (a); i < (b); i ++)
#define rrep(i, a, b) for(ll i = (b); i --> (a); )
#define all(x) begin(x), end(x)
#define fst first
#define snd second
#define pb push_back
template<class T> using V = vector<T>;
template<class T, std::size_t N> using AR = array<T, N>;
namespace IO {
template<class... Ts> void in(Ts&... t);
[[maybe_unused]] void print(){}
template<class T, class... Ts> void print(const T& t, const Ts&... ts);
template<class... Ts> void out(const Ts&... ts){ print(ts...); cout << '\n'; }
namespace IO{
#define VOID(a) decltype(void(a))
struct S{ S(){ cin.tie(nullptr)->sync_with_stdio(0); fixed(cout).precision(12); } }S;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){ in(get<idx>(t)...); }
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ ituple(t, make_index_sequence<tuple_size<T>::value>{}); }
template<class T> void o(const T& t){ o(t, P<4>{}); }
template<size_t N> void o(const char (&t)[N], P<4>){ cout << t; }
template<class T, size_t N> void o(const T (&t)[N], P<3>){ o(t[0]); for(size_t i = 1; i < N; i++){ o(' '); o(t[i]); } }
template<class T> auto o(const T& t, P<2>) -> VOID(cout << t){ cout << t; }
template<class T> auto o(const T& t, P<1>) -> VOID(begin(t)){ bool first = 1; for(auto&& x : t) { if(first) first = 0; else o(' '); o(x); } }
template<class T, size_t... idx> void otuple(const T& t, index_sequence<idx...>){ print(get<idx>(t)...); }
template<class T> auto o(T& t, P<0>) -> VOID(tuple_size<T>{}){ otuple(t, make_index_sequence<tuple_size<T>::value>{}); }
#undef VOID
}
template<class... Ts> void in(Ts&... t){ (IO::i(t), ...); }
template<class T, class... Ts> void print(const T& t, const Ts&... ts){ IO::o(t); (IO::o((cout << ' ', ts)), ...); }
#undef unpack
constexpr ll debug_const(ll judge, ll debug) {
#ifdef DEBUG
return debug;
#else
return judge;
#endif
}
#ifdef DEBUG
ll __lg(ull x){ return 63 - __builtin_clzll(x); }
#define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...) void(0)
#endif
#define dbg debug
} using namespace IO;
#define MAIN
#include __FILE__
#endif