結果
問題 | No.2485 Add to Variables (Another) |
ユーザー |
![]() |
提出日時 | 2023-09-22 23:10:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 5,829 bytes |
コンパイル時間 | 4,169 ms |
コンパイル使用メモリ | 305,868 KB |
実行使用メモリ | 23,168 KB |
最終ジャッジ日時 | 2024-07-08 13:52:25 |
合計ジャッジ時間 | 7,147 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 39 |
ソースコード
#if __INCLUDE_LEVEL__ == 0#include __BASE_FILE__namespace {using Fp = atcoder::modint998244353;Comb<Fp> comb(1e6);void solve() {int n, m;cin >> tie(n, m);vector<int> a(n);cin >> a;if (n == 1) {print(comb.binom(m, a[0]));return;}for (int i : per(1, n)) {a[i] -= a[i - 1];}vector<vector<Fp>> q;for (int i : rep(1, n)) {vector<Fp> f(m + 1);for (int c : rep1(0, m)) {int d = c - a[i];if (0 <= c + d && c + d <= m) {f[c + d] = comb.recip_fact(c) * comb.recip_fact(d);}}q.push_back(f);}for (int qi = 0; qi + 2 <= len(q); qi += 2) {q.push_back(atcoder::convolution(q[qi], q[qi + 1]));q.back().resize(m + 1);}int a1 = ALL(accumulate, a | views::drop(1), 0);vector<Fp> f(m + 1);for (int s : rep1(0, m)) {if ((a1 - s) & 1) {continue;}int c = a[0] + (a1 - s) / 2;int d = m - s - c;if (0 <= c + d && c + d <= m) {f[c + d] = comb.recip_fact(c) * comb.recip_fact(d);}}f = atcoder::convolution(f, q.back());print(f[m] * comb.fact(m));}} // namespaceint main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();}#else // __INCLUDE_LEVEL__#include <bits/stdc++.h>using namespace std;#define ALL(f, r, ...) \[&](auto&& _) { return f(begin(_), end(_), ##__VA_ARGS__); }(r)#include <atcoder/convolution>template <class T>vector<T> make_vector_for_overwrite(int n) {static_assert(is_trivially_destructible_v<T>);vector<T> v;v.reserve(n);auto p = (T**)&v;p[1] = p[2];return v;}template <class T>class Comb {public:Comb() = default;explicit Comb(int max_n): fact_(make_vector_for_overwrite<T>(max_n + 1)),recip_fact_(make_vector_for_overwrite<T>(max_n + 1)) {fact_[0] = 1;for (int n = 1; n <= max_n; ++n) {fact_[n] = fact_[n - 1] * n;}recip_fact_[max_n] = 1 / fact_[max_n];for (int n = max_n; 1 <= n; --n) {recip_fact_[n - 1] = n * recip_fact_[n];}}T recip(int n) const {assert(n);return n < 0 ? -recip(-n) : recip_fact_[n] * fact_[n - 1];}T fact(int n) const {assert(0 <= n);return fact_[n];}T recip_fact(int n) const { return n < 0 ? 0 : recip_fact_[n]; }T falling_fact(int n, int k) const {assert(0 <= n || n < k);if (n < 0) {T t = falling_fact(k - n - 1, k);return k & 1 ? -t : t;}return n < k ? 0 : recip_fact(n - k) * fact(n);}T recip_falling_fact(int n, int k) const {assert(n < 0 || k <= n);return falling_fact(n - k, -k);}T rising_fact(int n, int k) const {assert(n <= 0 || 0 < n + k);return falling_fact(n + k - 1, k);}T recip_rising_fact(int n, int k) const {assert(0 < n || n + k <= 0);return falling_fact(n - 1, -k);}T binom(int n, int k) const {if ((n < 0) ^ (k < 0) ^ (n < k)) {return 0;}if (n < 0 && k < 0) {k = n - k;}return recip_fact(k) * falling_fact(n, k);}T recip_binom(int n, int k) const {assert((0 <= n) ^ (0 <= k) ^ (k <= n));k = max(k, n - k);return recip_falling_fact(n, k) * fact(k);}T multiset(int n, int k) const { return binom(n + k - 1, k); }T recip_multiset(int n, int k) const {assert((0 < n) ^ (0 <= k) ^ (0 < n + k));return recip_binom(n + k - 1, k);}private:vector<T> fact_;vector<T> recip_fact_;};template <class T, class U = T>bool chmin(T& x, U&& y) {return y < x && (x = forward<U>(y), true);}template <class T, class U = T>bool chmax(T& x, U&& y) {return x < y && (x = forward<U>(y), true);}namespace std {template <class T1, class T2>istream& operator>>(istream& is, pair<T1, T2>& p) {return is >> p.first >> p.second;}template <class... Ts>istream& operator>>(istream& is, tuple<Ts...>& t) {return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);}template <class... Ts>istream& operator>>(istream& is, tuple<Ts&...>&& t) {return is >> t;}template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr>auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) {for (auto&& e : r) {is >> e;}return is;}template <class T1, class T2>ostream& operator<<(ostream& os, const pair<T1, T2>& p) {return os << p.first << ' ' << p.second;}template <class... Ts>ostream& operator<<(ostream& os, const tuple<Ts...>& t) {auto f = [&os](const auto&... xs) -> ostream& {[[maybe_unused]] auto sep = "";((os << exchange(sep, " ") << xs), ...);return os;};return apply(f, t);}template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr>auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) {auto sep = "";for (auto&& e : r) {os << exchange(sep, " ") << e;}return os;}} // namespace stdnamespace atcoder {template <class T, internal::is_modint_t<T>* = nullptr>istream& operator>>(istream& is, T& x) {int v;is >> v;x = T::raw(v);return is;}template <class T, internal::is_modint_t<T>* = nullptr>ostream& operator<<(ostream& os, const T& x) {return os << x.val();}} // namespace atcodertemplate <class... Ts>void print(Ts&&... xs) {cout << tie(xs...) << '\n';}inline auto rep(int l, int r) { return views::iota(min(l, r), r); }inline auto rep(int n) { return rep(0, n); }inline auto rep1(int l, int r) { return rep(l, r + 1); }inline auto rep1(int n) { return rep(1, n + 1); }inline auto per(int l, int r) { return rep(l, r) | views::reverse; }inline auto per(int n) { return per(0, n); }inline auto per1(int l, int r) { return per(l, r + 1); }inline auto per1(int n) { return per(1, n + 1); }inline auto len = ranges::ssize;#endif // __INCLUDE_LEVEL__