結果

問題 No.2959 Dolls' Tea Party
ユーザー 👑 binapbinap
提出日時 2024-10-28 21:31:43
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,669 bytes
コンパイル時間 5,486 ms
コンパイル使用メモリ 285,108 KB
実行使用メモリ 22,944 KB
最終ジャッジ日時 2024-10-29 00:12:29
合計ジャッジ時間 9,999 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

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

#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" : " "); return
    os;}
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){return
    true;}); 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=9928
struct 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 0
P 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 1
P 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 0
P 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> frequency_a(K + 1);
rep(i, n){
int a;
cin >> a;
frequency_a[min(a, K)]++;
}
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(int i = 1; i <= K; i++){
int p = gcd(i, K);
int q = K / p;
vector<int> frequency_b(p + 1);
for(int a = 1; a <= K; a++){
int b = a / q;
frequency_b[b] += frequency_a[a];
}
FPS g_log(p + 1);
for(int b = 1; b <= p; b++){
g_log += f_log[b] * mint(frequency_b[b]);
}
FPS g = g_log.exp();
ans += g[p] * facts(p);
}
cout << ans / K << "\n";
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0