結果
| 問題 | No.3046 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);
}
}