結果
| 問題 |
No.1861 Required Number
|
| コンテスト | |
| ユーザー |
 stoq
|
| 提出日時 | 2022-03-04 21:44:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,114 ms / 2,500 ms |
| コード長 | 11,239 bytes |
| コンパイル時間 | 6,072 ms |
| コンパイル使用メモリ | 279,760 KB |
| 最終ジャッジ日時 | 2025-01-28 05:04:11 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 42 MLE * 4 |
ソースコード
#define MOD_TYPE 2
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
//#include <atcoder/modint>
//#include <atcoder/lazysegtree>
//#include <atcoder/segtree>
using namespace atcoder;
#if 0
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using Int = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;
#endif
#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <typename T>
using extset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#if 1
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#pragma region Macros
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;
#if MOD_TYPE == 1
constexpr ll MOD = ll(1e9 + 7);
#else
#if MOD_TYPE == 2
constexpr ll MOD = 998244353;
#else
constexpr ll MOD = 1000003;
#endif
#endif
using mint = static_modint<MOD>;
constexpr int INF = (int)1e9 + 10;
constexpr ll LINF = (ll)4e18;
constexpr double PI = acos(-1.0);
constexpr double EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};
#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
struct io_init {
io_init() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << setprecision(30) << setiosflags(ios::fixed);
};
} io_init;
template <typename T>
inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T>
inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
inline ll floor(ll a, ll b) {
if (b < 0) a *= -1, b *= -1;
if (a >= 0) return a / b;
return -((-a + b - 1) / b);
}
inline ll ceil(ll a, ll b) { return floor(a + b - 1, b); }
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val) {
fill((T *)array, (T *)(array + N), val);
}
template <typename T>
vector<T> compress(vector<T> &v) {
vector<T> val = v;
sort(all(val)), val.erase(unique(all(val)), val.end());
for (auto &&vi : v) vi = lower_bound(all(val), vi) - val.begin();
return val;
}
template <typename T, typename U>
constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept {
is >> p.first >> p.second;
return is;
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> p) noexcept {
os << p.first << " " << p.second;
return os;
}
ostream &operator<<(ostream &os, mint m) {
os << m.val();
return os;
}
ostream &operator<<(ostream &os, modint m) {
os << m.val();
return os;
}
template <typename T>
constexpr istream &operator>>(istream &is, vector<T> &v) noexcept {
for (int i = 0; i < v.size(); i++) is >> v[i];
return is;
}
template <typename T>
constexpr ostream &operator<<(ostream &os, vector<T> &v) noexcept {
for (int i = 0; i < v.size(); i++)
os << v[i] << (i + 1 == v.size() ? "" : " ");
return os;
}
template <typename T>
constexpr void operator--(vector<T> &v, int) noexcept {
for (int i = 0; i < v.size(); i++) v[i]--;
}
random_device seed_gen;
mt19937_64 engine(seed_gen());
struct BiCoef {
vector<mint> fact_, inv_, finv_;
BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
for (int i = 2; i < n; i++) {
fact_[i] = fact_[i - 1] * i;
inv_[i] = -inv_[MOD % i] * (MOD / i);
finv_[i] = finv_[i - 1] * inv_[i];
}
}
mint C(ll n, ll k) const noexcept {
if (n < k || n < 0 || k < 0) return 0;
return fact_[n] * finv_[k] * finv_[n - k];
}
mint P(ll n, ll k) const noexcept { return C(n, k) * fact_[k]; }
mint H(ll n, ll k) const noexcept { return C(n + k - 1, k); }
mint Ch1(ll n, ll k) const noexcept {
if (n < 0 || k < 0) return 0;
mint res = 0;
for (int i = 0; i < n; i++)
res += C(n, i) * mint(n - i).pow(k) * (i & 1 ? -1 : 1);
return res;
}
mint fact(ll n) const noexcept {
if (n < 0) return 0;
return fact_[n];
}
mint inv(ll n) const noexcept {
if (n < 0) return 0;
return inv_[n];
}
mint finv(ll n) const noexcept {
if (n < 0) return 0;
return finv_[n];
}
};
BiCoef bc(200010);
#pragma endregion
// -------------------------------
#pragma region FPS
// 引用：
// https://opt-cp.com/fps-implementation/
#define fastprod 1
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
template <class T>
struct FormalPowerSeries : vector<T> {
using vector<T>::vector;
using vector<T>::operator=;
using F = FormalPowerSeries;
F operator-() const {
F res(*this);
for (auto &e : res) e = -e;
return res;
}
F &operator*=(const T &g) {
for (auto &e : *this) e *= g;
return *this;
}
F &operator/=(const T &g) {
assert(g != T(0));
*this *= g.inv();
return *this;
}
F &operator+=(const F &g) {
int n = (*this).size(), m = g.size();
repi(i, min(n, m))(*this)[i] += g[i];
return *this;
}
F &operator-=(const F &g) {
int n = (*this).size(), m = g.size();
repi(i, min(n, m))(*this)[i] -= g[i];
return *this;
}
F &operator<<=(const int d) {
int n = (*this).size();
(*this).insert((*this).begin(), d, 0);
(*this).resize(n);
return *this;
}
F &operator>>=(const int d) {
int n = (*this).size();
(*this).erase((*this).begin(), (*this).begin() + min(n, d));
(*this).resize(n);
return *this;
}
F inv(int d = -1) const {
int n = (*this).size();
assert(n != 0 && (*this)[0] != 0);
if (d == -1) d = n;
assert(d > 0);
F res{(*this)[0].inv()};
while (res.size() < d) {
int m = size(res);
F f(begin(*this), begin(*this) + min(n, 2 * m));
F r(res);
f.resize(2 * m), internal::butterfly(f);
r.resize(2 * m), internal::butterfly(r);
repi(i, 2 * m) f[i] *= r[i];
internal::butterfly_inv(f);
f.erase(f.begin(), f.begin() + m);
f.resize(2 * m), internal::butterfly(f);
repi(i, 2 * m) f[i] *= r[i];
internal::butterfly_inv(f);
T iz = T(2 * m).inv();
iz *= -iz;
repi(i, m) f[i] *= iz;
res.insert(res.end(), f.begin(), f.begin() + m);
}
return {res.begin(), res.begin() + d};
}
// fast: FMT-friendly modulus only
#if fastprod
F &operator*=(const F &g) {
int n = (*this).size();
*this = convolution(*this, g);
(*this).resize(n);
return *this;
}
F &operator/=(const F &g) {
int n = (*this).size();
*this = convolution(*this, g.inv(n));
(*this).resize(n);
return *this;
}
#else
F &operator*=(const F &g) {
int n = (*this).size(), m = g.size();
drep(i, n) {
(*this)[i] *= g[0];
REPI(j, 1, min(i + 1, m))(*this)[i] += (*this)[i - j] * g[j];
}
return *this;
}
F &operator/=(const F &g) {
assert(g[0] != T(0));
T ig0 = g[0].inv();
int n = (*this).size(), m = g.size();
repi(i, n) {
REPI(j, 1, min(i + 1, m))(*this)[i] -= (*this)[i - j] * g[j];
(*this)[i] *= ig0;
}
return *this;
}
#endif
// sparse
F &operator*=(vector<pair<int, T>> g) {
int n = (*this).size();
auto [d, c] = g.front();
if (d == 0)
g.erase(g.begin());
else
c = 0;
drep(i, n) {
(*this)[i] *= c;
for (auto &[j, b] : g) {
if (j > i) break;
(*this)[i] += (*this)[i - j] * b;
}
}
return *this;
}
F &operator/=(vector<pair<int, T>> g) {
int n = (*this).size();
auto [d, c] = g.front();
assert(d == 0 && c != T(0));
T ic = c.inv();
g.erase(g.begin());
repi(i, n) {
for (auto &[j, b] : g) {
if (j > i) break;
(*this)[i] -= (*this)[i - j] * b;
}
(*this)[i] *= ic;
}
return *this;
}
// multiply and divide (1 + cz^d)
void multiply(const int d, const T c) {
int n = (*this).size();
if (c == T(1))
drep(i, n - d)(*this)[i + d] += (*this)[i];
else if (c == T(-1))
drep(i, n - d)(*this)[i + d] -= (*this)[i];
else
drep(i, n - d)(*this)[i + d] += (*this)[i] * c;
}
void divide(const int d, const T c) {
int n = (*this).size();
if (c == T(1))
repi(i, n - d)(*this)[i + d] -= (*this)[i];
else if (c == T(-1))
repi(i, n - d)(*this)[i + d] += (*this)[i];
else
repi(i, n - d)(*this)[i + d] -= (*this)[i] * c;
}
T eval(const T &a) const {
T x(1), res(0);
for (auto e : *this) res += e * x, x *= a;
return res;
}
void differentiate() {
int n = (*this).size();
(*this) >>= 1;
REPI(i, 1, n - 1)(*this)[i] *= (i + 1);
}
void integrate(bool ext = true) {
if (ext) (*this).push_back(0);
int n = (*this).size();
(*this) <<= 1;
REPI(i, 1, n)(*this)[i] *= bc.inv(i);
}
F operator*(const T &g) const { return F(*this) *= g; }
F operator/(const T &g) const { return F(*this) /= g; }
F operator+(const F &g) const { return F(*this) += g; }
F operator-(const F &g) const { return F(*this) -= g; }
F operator<<(const int d) const { return F(*this) <<= d; }
F operator>>(const int d) const { return F(*this) >>= d; }
F operator*(const F &g) const { return F(*this) *= g; }
F operator/(const F &g) const { return F(*this) /= g; }
F operator*(vector<pair<int, T>> g) const { return F(*this) *= g; }
F operator/(vector<pair<int, T>> g) const { return F(*this) /= g; }
};
using fps = FormalPowerSeries<mint>;
using sfps = vector<pair<int, mint>>;
void add_ext(fps &f, fps &g) {
f.resize(max(f.size(), g.size()));
f += g;
}
void prod_ext(fps &f, fps &g) {
f.resize(f.size() + g.size() - 1, 0);
f *= g;
}
void prod_ext(fps &f, sfps &g) {
int m = 0;
for (auto [d, c] : g) {
if (m < d) m = d;
}
f.resize(f.size() + m);
f *= g;
}
#pragma endregion
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
cin >> a;
vector<fps> L(n + 1), R(n + 1);
fps e(k + 1, 0);
e[0] = 1;
L[0] = R[n] = e;
rep(i, n) {
L[i + 1] = L[i];
L[i + 1].multiply(a[i], 1);
}
for (int i = n; i > 0; i--) {
R[i - 1] = R[i];
R[i - 1].multiply(a[i - 1], 1);
}
if (L[n][k].val() == 0) {
cout << -1 << "\n";
return;
}
int cnt = 0;
rep(i, n) {
fps f = L[i] * R[i + 1];
if (f[k].val() == 0) cnt++;
}
cout << cnt << "\n";
}
int main() { solve(); }