結果
問題 | No.2959 Dolls' Tea Party |
ユーザー |
👑 |
提出日時 | 2024-10-28 21:27:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 8,573 bytes |
コンパイル時間 | 5,188 ms |
コンパイル使用メモリ | 291,660 KB |
実行使用メモリ | 24,100 KB |
最終ジャッジ日時 | 2024-10-29 00:12:28 |
合計ジャッジ時間 | 10,039 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 TLE * 1 -- * 30 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;using namespace atcoder;typedef long long ll;typedef vector<int> vi;typedef vector<long long> vl;typedef vector<vector<int>> vvi;typedef vector<vector<long long>> vvl;typedef long double ld;typedef pair<int, int> P;ostream& operator<<(ostream& os, const modint& a) {os << a.val(); return os;}template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); returnos;}template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : "");return os;}template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){returntrue;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n- 1 ? "\n" : " "); return os;}template<typename T> void chmin(T& a, T b){a = min(a, b);}template<typename T> void chmax(T& a, T b){a = max(a, b);}using mint = modint998244353;// combination mod prime// https://youtu.be/8uowVvQ_-Mo?t=6002// https://youtu.be/Tgd_zLfRZOQ?t=9928struct modinv {int n; vector<mint> d;modinv(): n(2), d({0,1}) {}mint operator()(int i) {while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;return d[i];}mint operator[](int i) const { return d[i];}} invs;struct modfact {int n; vector<mint> d;modfact(): n(2), d({1,1}) {}mint operator()(int i) {while (n <= i) d.push_back(d.back()*n), ++n;return d[i];}mint operator[](int i) const { return d[i];}} facts;struct modfactinv {int n; vector<mint> d;modfactinv(): n(2), d({1,1}) {}mint operator()(int i) {while (n <= i) d.push_back(d.back()*invs(n)), ++n;return d[i];}mint operator[](int i) const { return d[i];}} ifacts;mint comb(int n, int k) {if (n < k || k < 0) return 0;return facts(n)*ifacts(k)*ifacts(n-k);}template< typename T >struct FormalPowerSeries : vector< T > {using vector< T >::vector;using P = FormalPowerSeries;template<class...Args> FormalPowerSeries(Args...args): vector<T>(args...) {}FormalPowerSeries(initializer_list<T> a): vector<T>(a.begin(),a.end()) {}using MULT = function< P(P, P) >;static MULT &get_mult() {static MULT mult = [&](P a, P b){P res(convolution(a, b));return res;};return mult;}static void set_fft(MULT f) {get_mult() = f;}void shrink() {while(this->size() && this->back() == T(0)) this->pop_back();}P operator+(const P &r) const { return P(*this) += r; }P operator+(const T &v) const { return P(*this) += v; }P operator-(const P &r) const { return P(*this) -= r; }P operator-(const T &v) const { return P(*this) -= v; }P operator*(const P &r) const { return P(*this) *= r; }P operator*(const T &v) const { return P(*this) *= v; }P operator/(const P &r) const { return P(*this) /= r; }P operator%(const P &r) const { return P(*this) %= r; }P &operator+=(const P &r) {if(r.size() > this->size()) this->resize(r.size());for(int i = 0; i < int(r.size()); i++) (*this)[i] += r[i];return *this;}P &operator+=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] += r;return *this;}P &operator-=(const P &r) {if(r.size() > this->size()) this->resize(r.size());for(int i = 0; i < int(r.size()); i++) (*this)[i] -= r[i];// shrink();return *this;}P &operator-=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] -= r;// shrink();return *this;}P &operator*=(const T &v) {const int n = (int) this->size();for(int k = 0; k < n; k++) (*this)[k] *= v;return *this;}P &operator*=(const P &r) {if(this->empty() || r.empty()) {this->clear();return *this;}assert(get_mult() != nullptr);return *this = get_mult()(*this, r);}P &operator%=(const P &r) {return *this -= *this / r * r;}P operator-() const {P ret(this->size());for(int i = 0; i < int(this->size()); i++) ret[i] = -(*this)[i];return ret;}P &operator/=(const P &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(n);}P pre(int sz) const {return P(begin(*this), begin(*this) + min((int) this->size(), sz));}P operator>>(int sz) const {if((int)this->size() <= sz) return {};P ret(*this);ret.erase(ret.begin(), ret.begin() + sz);return ret;}P operator<<(int sz) const {P ret(*this);ret.insert(ret.begin(), sz, T(0));return ret;}P rev(int deg = -1) const {P ret(*this);if(deg != -1) ret.resize(deg, T(0));reverse(begin(ret), end(ret));return ret;}P diff() const {const int n = (int) this->size();P ret(max(0, n - 1));for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);return ret;}P integral() const {const int n = (int) this->size();P ret(n + 1);ret[0] = T(0);for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);return ret;}// F(0) must not be 0P inv(int deg = -1) const {assert(((*this)[0]) != T(0));const int n = (int) this->size();if(deg == -1) deg = n;P ret({T(1) / (*this)[0]});for(int i = 1; i < deg; i <<= 1) {ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);}return ret.pre(deg);}// F(0) must be 1P log(int deg = -1) const {assert((*this)[0] == T(1));const int n = (int) this->size();if(deg == -1) deg = n;return (this->diff() * this->inv(deg)).pre(deg - 1).integral();}// F(0) must be 0P exp(int deg = -1) const {assert((*this)[0] == T(0));const int n = (int) this->size();if(deg == -1) deg = n;P ret({T(1)});for(int i = 1; i < deg; i <<= 1) {ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);}return ret.pre(deg);}P pow(int k, int deg = -1) const {const int n = (int) this->size();if(deg == -1) deg = n;for(int i = 0; i < n; i++) {if((*this)[i] != T(0)) {T rev = T(1) / (*this)[i];P C(*this * rev);P D(n - i);for(int j = i; j < n; j++) D[j - i] = C[j];D = (D.log(deg) * T(k)).exp() * (*this)[i].pow(k);P E(deg);if(i * k > deg) return E;auto S = i * k;for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];return E;}}return *this;}};template<typename T>void infer(vector<T> v){for(auto& a : v) infer(a); cout << "\n";}using FPS = FormalPowerSeries<mint>;int main(){int n, K;cin >> n >> K;mint ans = 0;vector<int> a(n);cin >> a;map<int, int> frequency_p;for(int i = 1; i <= K; i++){int p = gcd(K, i);frequency_p[p]++;}vector<FPS> f(K + 1, FPS(K + 1));f[0][0] = 1;for(int k = 1; k <= K; k++){f[k] = f[k - 1];f[k][k] = ifacts(k);}vector<FPS> f_log(K + 1, FPS(K + 1));rep(k, K + 1) f_log[k] = f[k].log();for(auto [p, c] : frequency_p){int q = K / p;vector<int> frequency_b(p + 1);FPS g_log(p + 1);rep(i, n){g_log += f_log[min(a[i] / q, p)];}FPS g = g_log.exp();ans += g[p] * facts(p) * c;}cout << ans / K << "\n";return 0;}