結果
問題 | No.8046 yukicoderの過去問 |
ユーザー | keijak |
提出日時 | 2021-12-27 06:30:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 285 ms / 2,000 ms |
コード長 | 9,721 bytes |
コンパイル時間 | 4,136 ms |
コンパイル使用メモリ | 260,020 KB |
実行使用メモリ | 13,200 KB |
最終ジャッジ日時 | 2024-09-24 23:36:16 |
合計ジャッジ時間 | 7,256 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 274 ms
13,072 KB |
testcase_01 | AC | 273 ms
13,068 KB |
testcase_02 | AC | 281 ms
13,076 KB |
testcase_03 | AC | 282 ms
13,072 KB |
testcase_04 | AC | 274 ms
13,072 KB |
testcase_05 | AC | 275 ms
13,200 KB |
testcase_06 | AC | 281 ms
12,948 KB |
testcase_07 | AC | 273 ms
13,076 KB |
testcase_08 | AC | 285 ms
13,076 KB |
ソースコード
#include <bits/stdc++.h> #define REP_(i, a_, b_, a, b, ...) for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using Int = long long; using Uint = unsigned long long; using Real = long double; #include <atcoder/convolution> #include <atcoder/math> #include <atcoder/modint> using Mint = atcoder::modint1000000007; std::ostream &operator<<(std::ostream &os, const Mint &m) { return os << m.val(); } template<typename T, typename U> inline bool chmax(T &a, U b) { return a < b and ((a = std::move(b)), true); } template<typename T, typename U> inline bool chmin(T &a, U b) { return a > b and ((a = std::move(b)), true); } template<typename T> inline int ssize(const T &a) { return (int) a.size(); } struct Void {}; template<class T> inline std::ostream &print_one(const T &x, char endc) { if constexpr (std::is_same<T, Void>::value) { return std::cout; // print nothing } else if constexpr (std::is_same<T, bool>::value) { return std::cout << (x ? "Yes" : "No") << endc; } else { return std::cout << x << endc; } } template<class T> inline std::ostream &print(const T &x) { return print_one(x, '\n'); } template<typename T, typename... Ts> std::ostream &print(const T &head, Ts... tail) { return print_one(head, ' '), print(tail...); } inline std::ostream &print() { return std::cout << '\n'; } template<typename Container> std::ostream &print_seq(const Container &seq, const char *sep = " ", const char *ends = "\n", std::ostream &os = std::cout) { const auto itl = std::begin(seq), itr = std::end(seq); for (auto it = itl; it != itr; ++it) { if (it != itl) os << sep; os << *it; } return os << ends; } struct CastInput { template<typename T> operator T() const { T x; std::cin >> x; return x; } struct Sized { std::size_t n; template<typename T> operator T() const { T x(n); for (auto &e: x) std::cin >> e; return x; } }; Sized operator()(std::size_t n) const { return {n}; } } in; #ifdef MY_DEBUG #include "debug_dump.hpp" #include "backward.hpp" backward::SignalHandling kSignalHandling; #else #define DUMP(...) #define cerr if(false)cerr #endif // T: modint template<typename T, int DMAX> struct ArbitraryModMult { using value_type = T; static_assert(atcoder::internal::is_modint<T>::value); static constexpr int dmax() { return DMAX; } static std::vector<T> convolution(const std::vector<T> &x, const std::vector<T> &y, int size_limit) { std::vector<int> xv(x.size()); std::vector<int> yv(y.size()); for (int i = 0; i < (int) x.size(); ++i) xv[i] = x[i].val(); for (int i = 0; i < (int) y.size(); ++i) yv[i] = y[i].val(); constexpr int M1 = 167772161, M2 = 469762049, M3 = 1224736769; const auto z1 = atcoder::convolution<M1>(xv, yv); const auto z2 = atcoder::convolution<M2>(xv, yv); const auto z3 = atcoder::convolution<M3>(xv, yv); const Int m1_inv_m2 = atcoder::inv_mod(M1, M2); const Int m12_inv_m3 = atcoder::inv_mod(Int(M1) * M2, M3); const Int m12 = Int(M1) * M2 % T::mod(); const int n = std::min<int>(x.size() + y.size() - 1, size_limit); std::vector<T> res(n); for (int i = 0; i < n; ++i) { atcoder::static_modint<M2> v1 = z2[i] - z1[i]; v1 *= m1_inv_m2; const Int w1 = v1.val() * Int(M1); atcoder::static_modint<M3> v2 = z3[i] - z1[i] - w1; v2 *= m12_inv_m3; res[i] = z1[i] + w1 + (v2.val() * m12); } return res; } static std::vector<T> multiply(const std::vector<T> &x, const std::vector<T> &y) { return convolution(x, y, dmax() + 1); } static std::vector<T> invert(const std::vector<T> &x) { assert(x[0].val() != 0); // must be invertible const int n = x.size(); std::vector<T> res(n); res[0] = T(1) / x[0]; for (int i = 1; i < n; i <<= 1) { const int m = std::min(2 * i, n); std::vector<T> f(2 * i), g(2 * i); for (int j = 0; j < m; ++j) f[j] = x[j]; for (int j = 0; j < i; ++j) g[j] = res[j]; f = convolution(f, g, 2 * i); f.resize(2 * i); for (int j = 0; j < i; ++j) f[j] = 0; f = convolution(f, g, 2 * i); for (int j = i; j < m; ++j) res[j] = -f[j]; } return res; } }; template<typename Mult> struct DenseFPS { using T = typename Mult::value_type; static constexpr int dmax() { return Mult::dmax(); } // Coefficients of terms from x^0 to x^DMAX. std::vector<T> coeff_; DenseFPS() : coeff_(1, 0) {} // zero explicit DenseFPS(std::vector<T> c) : coeff_(std::move(c)) { while (size() > dmax() + 1) coeff_.pop_back(); assert(size() > 0); } DenseFPS(std::initializer_list<T> c) : coeff_(c.begin(), c.end()) { while (size() > dmax() + 1) coeff_.pop_back(); assert(size() > 0); } // size <= dmax + 1 inline int size() const { return static_cast<int>(coeff_.size()); } // Returns the coefficient of x^k. inline T operator[](int k) const { return (k >= size()) ? 0 : coeff_[k]; } // Removes trailing zeros. void shrink() { while (coeff_.size() > 1 and coeff_.back() == T(0)) coeff_.pop_back(); } DenseFPS &operator+=(const T &scalar) { coeff_[0] += scalar; return *this; } friend DenseFPS operator+(const DenseFPS &f, const T &scalar) { return DenseFPS(f) += scalar; } DenseFPS &operator+=(const DenseFPS &other) { if (size() < other.size()) coeff_.resize(other.size()); for (int i = 0; i < other.size(); ++i) coeff_[i] += other[i]; return *this; } friend DenseFPS operator+(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) += g; } DenseFPS &operator-=(const DenseFPS &other) { if (size() < other.size()) coeff_.resize(other.size()); for (int i = 0; i < other.size(); ++i) coeff_[i] -= other[i]; return *this; } friend DenseFPS operator-(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) -= g; } DenseFPS operator-() const { return *this * -1; } DenseFPS &operator*=(const T &scalar) { for (auto &x: coeff_) x *= scalar; return *this; } friend DenseFPS operator*(const DenseFPS &f, const T &scalar) { return DenseFPS(f) *= scalar; } friend DenseFPS operator*(const T &scalar, const DenseFPS &g) { return DenseFPS{scalar} *= g; } DenseFPS &operator*=(const DenseFPS &other) { return *this = DenseFPS(Mult::multiply(std::move(this->coeff_), other.coeff_)); } friend DenseFPS operator*(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(Mult::multiply(f.coeff_, g.coeff_)); } // Multiplies by x^k (with truncation). void shift_inplace(int k) { if (k > 0) { if (size() <= dmax()) { coeff_.resize(std::min(size() + k, dmax() + 1), 0); } for (int i = size() - 1; i >= k; --i) { coeff_[i] = coeff_[i - k]; } for (int i = k - 1; i >= 0; --i) { coeff_[i] = 0; } } else if (k < 0) { // If coefficients of degrees higher than dmax() were truncated // beforehand, you lose the information. Ensure dmax() is big enough. coeff_.erase(coeff_.begin(), coeff_.begin() + std::min(-k, size())); } } // Multiplies by x^k. DenseFPS shift(int k) const { DenseFPS res = *this; res.shift_inplace(k); return res; } DenseFPS &operator/=(const T &scalar) { for (auto &x: coeff_) x /= scalar; return *this; } friend DenseFPS operator/(const DenseFPS &f, const T &scalar) { return DenseFPS(f) /= scalar; } friend DenseFPS operator/(const T &scalar, const DenseFPS &g) { return DenseFPS{scalar} /= g; } DenseFPS &operator/=(const DenseFPS &other) { int z = 0; const int msz = std::min(size(), other.size()); while (z < msz and (*this)[z] == T(0) and other[z] == T(0)) ++z; if (z == size()) { return *this; // 0/y == 0 regardless of y. } if (z == 0) { return *this *= DenseFPS(Mult::invert(other.coeff_)); } else { shift_inplace(-z); std::vector<T> y(other.coeff_.begin() + std::min(z, other.size()), other.coeff_.end()); return *this *= DenseFPS(Mult::invert(std::move(y))); } } friend DenseFPS operator/(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) /= g; } // Multiplies by (1 + c * x^k). void multiply2_inplace(int k, int c) { assert(k > 0); if (size() <= dmax()) { coeff_.resize(min(size() + k, dmax() + 1), 0); } for (int i = size() - 1; i >= k; --i) { coeff_[i] += coeff_[i - k] * c; } } // Multiplies by (1 + c * x^k). DenseFPS multiply2(int k, int c) const { DenseFPS res = *this; res.multiply2_inplace(k, c); return res; } // Divides by (1 + c * x^k). void divide2_inplace(int k, int c) { assert(k > 0); for (int i = k; i < size(); ++i) { coeff_[i] -= coeff_[i - k] * c; } } // Divides by (1 + c * x^k). DenseFPS divide2(int k, int c) const { DenseFPS res = *this; res.divide2_inplace(k, c); return res; } }; constexpr int D = 100005; using DF = DenseFPS<ArbitraryModMult<Mint, D>>; using namespace std; auto solve() { int K = in, n = in; vector<Mint> C(D, 0); REP(i, n) { int x = in; C[x] = 1; } DF f(C); auto g = DF{1} / (DF{1} - f); return g[K].val(); } int main() { std::ios::sync_with_stdio(false), cin.tie(nullptr); cout << std::fixed << std::setprecision(18); const int T = 1;//in; REP(t, T) { auto ans = solve(); print(ans); } }