結果

問題 No.2243 Coaching Schedule
ユーザー rniya
提出日時 2023-03-10 22:50:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,070 ms / 4,000 ms
コード長 19,064 bytes
コンパイル時間 4,002 ms
コンパイル使用メモリ 256,128 KB
最終ジャッジ日時 2025-02-11 08:56:30
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(x) (x).begin(), (x).end()
#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) void(0)
#endif
template <typename T> istream& operator>>(istream& is, vector<T>& v) {
for (T& x : v) is >> x;
return is;
}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
for (size_t i = 0; i < v.size(); i++) {
os << v[i] << (i + 1 == v.size() ? "" : " ");
}
return os;
}
template <typename T> T gcd(T x, T y) { return y != 0 ? gcd(y, x % y) : x; }
template <typename T> T lcm(T x, T y) { return x / gcd(x, y) * y; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int botbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int botbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(long long t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
long long MSK(int n) { return (1LL << n) - 1; }
template <class T> T ceil(T x, T y) {
assert(y >= 1);
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T> T floor(T x, T y) {
assert(y >= 1);
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <class T1, class T2> inline bool chmin(T1& a, T2 b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T1, class T2> inline bool chmax(T1& a, T2 b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T> void mkuni(vector<T>& v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
template <typename T> int lwb(const vector<T>& v, const T& x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }
const int INF = (1 << 30) - 1;
const long long IINF = (1LL << 60) - 1;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int MOD = 998244353;
// const int MOD = 1000000007;
#include <iostream>
#include "atcoder/modint"
namespace atcoder {
template <int MOD> std::istream& operator>>(std::istream& is, static_modint<MOD>& x) {
int64_t v;
x = static_modint<MOD>{(is >> v, v)};
return is;
}
template <int MOD> std::ostream& operator<<(std::ostream& os, const static_modint<MOD>& x) { return os << x.val(); }
template <int ID> std::ostream& operator<<(std::ostream& os, const dynamic_modint<ID>& x) { return os << x.val(); }
} // namespace atcoder
#include <cassert>
#include <vector>
template <typename T> struct Binomial {
Binomial(int MAX = 0) : n(1), facs(1, T(1)), finvs(1, T(1)), invs(1, T(1)) {
while (n <= MAX) extend();
}
T fac(int i) {
assert(i >= 0);
while (n <= i) extend();
return facs[i];
}
T finv(int i) {
assert(i >= 0);
while (n <= i) extend();
return finvs[i];
}
T inv(int i) {
assert(i >= 0);
while (n <= i) extend();
return invs[i];
}
T P(int n, int r) {
if (n < 0 || n < r || r < 0) return T(0);
return fac(n) * finv(n - r);
}
T C(int n, int r) {
if (n < 0 || n < r || r < 0) return T(0);
return fac(n) * finv(n - r) * finv(r);
}
T H(int n, int r) {
if (n < 0 || r < 0) return T(0);
return r == 0 ? 1 : C(n + r - 1, r);
}
T C_naive(int n, int r) {
if (n < 0 || n < r || r < 0) return T(0);
T res = 1;
r = std::min(r, n - r);
for (int i = 1; i <= r; i++) res *= inv(i) * (n--);
return res;
}
private:
int n;
std::vector<T> facs, finvs, invs;
inline void extend() {
int m = n << 1;
facs.resize(m);
finvs.resize(m);
invs.resize(m);
for (int i = n; i < m; i++) facs[i] = facs[i - 1] * i;
finvs[m - 1] = T(1) / facs[m - 1];
invs[m - 1] = finvs[m - 1] * facs[m - 2];
for (int i = m - 2; i >= n; i--) {
finvs[i] = finvs[i + 1] * (i + 1);
invs[i] = finvs[i] * facs[i - 1];
}
n = m;
}
};
#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <utility>
#include <vector>
#include "atcoder/convolution"
template <typename T> struct FormalPowerSeries : std::vector<T> {
private:
using std::vector<T>::vector;
using FPS = FormalPowerSeries;
void shrink() {
while (this->size() and this->back() == T(0)) this->pop_back();
}
FPS pre(size_t sz) const { return FPS(this->begin(), this->begin() + std::min(this->size(), sz)); }
FPS rev() const {
FPS ret(*this);
std::reverse(ret.begin(), ret.end());
return ret;
}
FPS operator>>(size_t sz) const {
if (this->size() <= sz) return {};
return FPS(this->begin() + sz, this->end());
}
FPS operator<<(size_t sz) const {
if (this->empty()) return {};
FPS ret(*this);
ret.insert(ret.begin(), sz, T(0));
return ret;
}
public:
FPS& operator+=(const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (size_t i = 0; i < r.size(); i++) (*this)[i] += r[i];
shrink();
return *this;
}
FPS& operator+=(const T& v) {
if (this->empty()) this->resize(1);
(*this)[0] += v;
shrink();
return *this;
}
FPS& operator-=(const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (size_t i = 0; i < r.size(); i++) (*this)[i] -= r[i];
shrink();
return *this;
}
FPS& operator-=(const T& v) {
if (this->empty()) this->resize(1);
(*this)[0] -= v;
shrink();
return *this;
}
FPS& operator*=(const FPS& r) {
auto res = atcoder::convolution(*this, r);
return *this = {res.begin(), res.end()};
}
FPS& operator*=(const T& v) {
for (auto& x : (*this)) x *= v;
shrink();
return *this;
}
FPS& operator/=(const FPS& r) {
if (this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev();
}
FPS& operator%=(const FPS& r) {
*this -= *this / r * r;
shrink();
return *this;
}
FPS operator+(const FPS& r) const { return FPS(*this) += r; }
FPS operator+(const T& v) const { return FPS(*this) += v; }
FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
FPS operator-(const T& v) const { return FPS(*this) -= v; }
FPS operator*(const FPS& r) const { return FPS(*this) *= r; }
FPS operator*(const T& v) const { return FPS(*this) *= v; }
FPS operator/(const FPS& r) const { return FPS(*this) /= r; }
FPS operator%(const FPS& r) const { return FPS(*this) %= r; }
FPS operator-() const {
FPS ret = *this;
for (auto& v : ret) v = -v;
return ret;
}
FPS differential() const {
const int n = (int)this->size();
FPS ret(std::max(0, n - 1));
for (int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);
return ret;
}
FPS integral() const {
const int n = (int)this->size();
FPS ret(n + 1);
ret[0] = T(0);
if (n > 0) ret[1] = T(1);
auto mod = T::mod();
for (int i = 2; i <= n; i++) ret[i] = -ret[mod % i] * (mod / i);
for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i];
return ret;
}
FPS inv(int deg = -1) const {
assert((*this)[0] != T(0));
const int n = (int)this->size();
if (deg == -1) deg = n;
FPS ret{(*this)[0].inv()};
ret.reserve(deg);
for (int d = 1; d < deg; d <<= 1) {
FPS f(d << 1), g(d << 1);
std::copy(this->begin(), this->begin() + std::min(n, d << 1), f.begin());
std::copy(ret.begin(), ret.end(), g.begin());
atcoder::internal::butterfly(f);
atcoder::internal::butterfly(g);
for (int i = 0; i < (d << 1); i++) f[i] *= g[i];
atcoder::internal::butterfly_inv(f);
std::fill(f.begin(), f.begin() + d, T(0));
atcoder::internal::butterfly(f);
for (int i = 0; i < (d << 1); i++) f[i] *= g[i];
atcoder::internal::butterfly_inv(f);
T iz = T(d << 1).inv();
iz *= -iz;
for (int i = d; i < std::min(d << 1, deg); i++) ret.push_back(f[i] * iz);
}
return ret.pre(deg);
}
FPS log(int deg = -1) const {
assert((*this)[0] == T(1));
if (deg == -1) deg = (int)this->size();
return (differential() * inv(deg)).pre(deg - 1).integral();
}
FPS sqrt(const std::function<T(T)>& get_sqrt, int deg = -1) const {
const int n = this->size();
if (deg == -1) deg = n;
if (this->empty()) return FPS(deg, 0);
if ((*this)[0] == T(0)) {
for (int i = 1; i < n; i++) {
if ((*this)[i] != T(0)) {
if (i & 1) return {};
if (deg - i / 2 <= 0) break;
auto ret = (*this >> i).sqrt(get_sqrt, deg - i / 2);
if (ret.empty()) return {};
ret = ret << (i / 2);
if ((int)ret.size() < deg) ret.resize(deg, T(0));
return ret;
}
}
return FPS(deg, T(0));
}
auto sqrtf0 = T(get_sqrt((*this)[0]));
if (sqrtf0 * sqrtf0 != (*this)[0]) return {};
FPS ret{sqrtf0};
T inv2 = T(2).inv();
for (int i = 1; i < deg; i <<= 1) ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
return ret.pre(deg);
}
/**
* @brief Exp of Formal Power Series
*
* @see https://arxiv.org/pdf/1301.5804.pdf
*/
FPS exp(int deg = -1) const {
assert(this->empty() or (*this)[0] == T(0));
if (this->size() == 0) return {};
if (this->size() == 1) return {T(1)};
if (deg == -1) deg = (int)this->size();
FPS inv;
inv.reserve(deg + 1);
inv.push_back(T(0));
inv.push_back(T(1));
auto inplace_integral = [&](FPS& F) -> void {
const int n = (int)F.size();
auto mod = T::mod();
while ((int)inv.size() <= n) {
int i = inv.size();
inv.push_back(-inv[mod % i] * (mod / i));
}
F.insert(F.begin(), T(0));
for (int i = 1; i <= n; i++) F[i] *= inv[i];
};
auto inplace_differential = [](FPS& F) -> void {
if (F.empty()) return;
F.erase(F.begin());
for (size_t i = 0; i < F.size(); i++) F[i] *= T(i + 1);
};
FPS f{1, (*this)[1]}, g{T(1)}, g_fft{T(1), T(1)};
for (int m = 2; m < deg; m <<= 1) {
const T iz1 = T(m).inv(), iz2 = T(m << 1).inv();
auto f_fft = f;
f_fft.resize(m << 1);
atcoder::internal::butterfly(f_fft);
{
// Step 2.a'
FPS _g(m);
for (int i = 0; i < m; i++) _g[i] = f_fft[i] * g_fft[i];
atcoder::internal::butterfly_inv(_g);
std::fill(_g.begin(), _g.begin() + (m >> 1), T(0));
atcoder::internal::butterfly(_g);
for (int i = 0; i < m; i++) _g[i] *= -g_fft[i] * iz1 * iz1;
atcoder::internal::butterfly_inv(_g);
g.insert(g.end(), _g.begin() + (m >> 1), _g.end());
g_fft = g;
g_fft.resize(m << 1);
atcoder::internal::butterfly(g_fft);
}
FPS x(this->begin(), this->begin() + std::min((int)this->size(), m));
{
// Step 2.b'
x.resize(m);
inplace_differential(x);
x.push_back(T(0));
atcoder::internal::butterfly(x);
}
{
// Step 2.c'
for (int i = 0; i < m; i++) x[i] *= f_fft[i] * iz1;
atcoder::internal::butterfly_inv(x);
}
{
// Step 2.d' and 2.e'
x -= f.differential();
x.resize(m << 1);
for (int i = 0; i < m - 1; i++) x[m + i] = x[i], x[i] = T(0);
atcoder::internal::butterfly(x);
for (int i = 0; i < (m << 1); i++) x[i] *= g_fft[i] * iz2;
atcoder::internal::butterfly_inv(x);
}
{
// Step 2.f'
x.pop_back();
inplace_integral(x);
for (int i = m; i < std::min((int)this->size(), m << 1); i++) x[i] += (*this)[i];
std::fill(x.begin(), x.begin() + m, T(0));
}
{
// Step 2.g' and 2.h'
atcoder::internal::butterfly(x);
for (int i = 0; i < (m << 1); i++) x[i] *= f_fft[i] * iz2;
atcoder::internal::butterfly_inv(x);
f.insert(f.end(), x.begin() + m, x.end());
}
}
return FPS{f.begin(), f.begin() + deg};
}
FPS pow(int64_t k, int deg = -1) const {
const int n = (int)this->size();
if (deg == -1) deg = n;
if (k == 0) {
auto res = FPS(deg, T(0));
res[0] = T(1);
return res;
}
for (int i = 0; i < n; i++) {
if ((*this)[i] != T(0)) {
if (i >= (deg + k - 1) / k) return FPS(deg, T(0));
T rev = (*this)[i].inv();
FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg) * ((*this)[i].pow(k));
ret = (ret << (i * k)).pre(deg);
if ((int)ret.size() < deg) ret.resize(deg, T(0));
return ret;
}
}
return FPS(deg, T(0));
}
T eval(T x) const {
T ret = 0, w = 1;
for (const auto& v : *this) ret += w * v, w *= x;
return ret;
}
static FPS product_of_polynomial_sequence(const std::vector<FPS>& fs) {
if (fs.empty()) return {T(1)};
auto comp = [](const FPS& f, const FPS& g) { return f.size() > g.size(); };
std::priority_queue<FPS, std::vector<FPS>, decltype(comp)> pq{comp};
for (const auto& f : fs) pq.emplace(f);
while (pq.size() > 1) {
auto f = pq.top();
pq.pop();
auto g = pq.top();
pq.pop();
pq.emplace(f * g);
}
return pq.top();
}
static FPS pow_sparse(const std::vector<std::pair<int, T>>& f, int64_t k, int n) {
assert(k >= 0);
int d = f.size(), offset = 0;
while (offset < d and f[offset].second == 0) offset++;
FPS res(n, 0);
if (offset == d) {
if (k == 0) res[0]++;
return res;
}
if (f[offset].first > 0) {
int deg = f[offset].first;
if (k > (n - 1) / deg) return res;
std::vector<std::pair<int, T>> g(f.begin() + offset, f.end());
for (auto& p : g) p.first -= deg;
auto tmp = pow_sparse(g, k, n - k * deg);
for (int i = 0; i < n - k * deg; i++) res[k * deg + i] = tmp[i];
return res;
}
std::vector<T> invs(n + 1);
invs[0] = T(0);
invs[1] = T(1);
auto mod = T::mod();
for (int i = 2; i <= n; i++) invs[i] = -invs[mod % i] * (mod / i);
res[0] = f[0].second.pow(k);
T coef = f[0].second.inv();
for (int i = 1; i < n; i++) {
for (int j = 1; j < d; j++) {
if (i - f[j].first < 0) break;
res[i] += f[j].second * res[i - f[j].first] * (T(k) * f[j].first - (i - f[j].first));
}
res[i] *= invs[i] * coef;
}
return res;
}
FPS taylor_shift(T c) const {
FPS f(*this);
const int n = f.size();
std::vector<T> fac(n), finv(n);
fac[0] = 1;
for (int i = 1; i < n; i++) {
fac[i] = fac[i - 1] * i;
f[i] *= fac[i];
}
finv[n - 1] = fac[n - 1].inv();
for (int i = n - 1; i > 0; i--) finv[i - 1] = finv[i] * i;
std::reverse(f.begin(), f.end());
FPS g(n);
g[0] = T(1);
for (int i = 1; i < n; i++) g[i] = g[i - 1] * c * finv[i] * fac[i - 1];
f = (f * g).pre(n);
std::reverse(f.begin(), f.end());
for (int i = 0; i < n; i++) f[i] *= finv[i];
return f;
}
};
#include <vector>
template <typename T> struct subproduct_tree {
using poly = FormalPowerSeries<T>;
int m;
std::vector<poly> prod;
subproduct_tree(const std::vector<T>& x) : m(x.size()) {
int k = 1;
while (k < m) k <<= 1;
prod.assign(k << 1, {1});
for (int i = 0; i < m; i++) prod[k + i] = {-x[i], 1};
for (int i = k - 1; i > 0; i--) prod[i] = prod[i << 1] * prod[i << 1 | 1];
}
int size() const { return prod.size() >> 1; }
poly mid_prod(const poly& a, const poly& b) const {}
std::vector<T> multipoint_evaluation(poly f) const {
std::vector<poly> rem(size() << 1);
rem[1] = f % prod[1];
for (int i = 2; i < size() + m; i++) rem[i] = rem[i >> 1] % prod[i];
std::vector<T> res(m);
for (int i = 0; i < m; i++) res[i] = (rem[size() + i].empty() ? 0 : rem[size() + i][0]);
return res;
}
};
using mint = atcoder::modint998244353;
using FPS = FormalPowerSeries<mint>;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
Binomial<mint> BINOM;
int N, M;
cin >> M >> N;
vector<int> cnt(M, 0);
for (int i = 0; i < N; i++) {
int A;
cin >> A;
cnt[--A]++;
}
vector<FPS> fs;
for (int i = 0; i < M; i++) {
for (int j = 0; j < cnt[i]; j++) {
FPS v = {-j, 1};
fs.emplace_back(v);
}
}
auto comb = FPS::product_of_polynomial_sequence(fs);
vector<mint> xs(N + 1);
iota(xs.begin(), xs.end(), 0);
subproduct_tree<mint> tree(xs);
auto dp = tree.multipoint_evaluation(comb);
vector<mint> sub(N + 1, 0);
auto dfs = [&](auto self, int l, int r) -> void {
if (r - l == 1) {
sub[l] *= BINOM.fac(l);
dp[l] -= sub[l];
return;
}
int m = (l + r) >> 1;
self(self, l, m);
FPS a, b;
for (int i = l; i < m; i++) a.emplace_back(dp[i] * BINOM.finv(i));
for (int i = 0; i < r - l; i++) b.emplace_back(BINOM.finv(i));
auto c = a * b;
for (int i = m; i < r and i - l < int(c.size()); i++) sub[i] += c[i - l];
self(self, m, r);
};
dfs(dfs, 0, N + 1);
mint ans = accumulate(dp.begin(), dp.end(), mint(0));
cout << ans << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0