結果
問題 | No.3095 Many Min Problems |
ユーザー |
|
提出日時 | 2025-04-06 16:27:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 700 ms / 2,000 ms |
コード長 | 4,609 bytes |
コンパイル時間 | 2,847 ms |
コンパイル使用メモリ | 210,604 KB |
実行使用メモリ | 64,640 KB |
最終ジャッジ日時 | 2025-04-06 16:27:30 |
合計ジャッジ時間 | 13,931 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
//https://yukicoder.me/problems/no/1145/editorial #include <bits/stdc++.h> using namespace std; template <class T, class Op = multiplies<T>> constexpr T power(T a, long long n, Op op = Op(), T e = {1}) { assert(n >= 0); while (n) { if (n & 1) e = op(e, a); if (n >>= 1) a = op(a, a); } return e; } template <class T> void ntt(vector<T>& a, bool inverse) { int n = size(a); assert((n & (n - 1)) == 0); if (n < 2) return; assert((T::mod - 1) % n == 0); static vector<T> w{1}, iw{1}; for (int m = size(w); m < n / 2; m *= 2) { static T root = 2; while (power(root, (T::mod - 1) / 2) == 1) root += 1; T dw = power(root, (T::mod - 1) / (4 * m)), idw = 1 / dw; w.resize(2 * m), iw.resize(2 * m); for (int i = 0; i < m; ++i) w[m + i] = w[i] * dw, iw[m + i] = iw[i] * idw; } if (not inverse) { for (int m = n; m >>= 1; ) { for (int s = 0, k = 0; s < n; s += 2 * m, ++k) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { T x = a[i], y = a[j] * w[k]; a[i] = x + y, a[j] = x - y; } } } } else { for (int m = 1; m < n; m *= 2) { for (int s = 0, k = 0; s < n; s += 2 * m, ++k) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { T x = a[i], y = a[j]; a[i] = x + y, a[j] = (x - y) * iw[k]; } } } auto inv = 1 / T(n); for (auto&& e : a) e *= inv; } } template <class T> vector<T> operator*(vector<T> a, vector<T> b) { if (empty(a) or empty(b)) return {}; int n = size(a), m = size(b), sz = 1 << __lg(2 * (n + m - 1) - 1); a.resize(sz), ntt(a, false); b.resize(sz), ntt(b, false); for (int i = 0; i < sz; ++i) a[i] *= b[i]; ntt(a, true), a.resize(n + m - 1); return a; } template <class T> vector<T> operator-(vector<T> a) { for (auto&& e : a) e = -e; return a; } template <class T> vector<T>& operator*=(vector<T>& a, const vector<T>& b) { return a = a * b; } template <class T> vector<T> inverse(const vector<T>& a) { assert(not empty(a) and not (a[0] == 0)); vector<T> b{1 / a[0]}; while (size(b) < size(a)) { vector<T> x(begin(a), begin(a) + min(size(a), 2 * size(b))); x *= b * b; b.resize(2 * size(b)); for (auto i = size(b) / 2; i < min(size(x), size(b)); ++i) b[i] = -x[i]; } return {begin(b), begin(b) + size(a)}; } template <class T> vector<T> derivative(const vector<T>& a) { vector<T> res(max((int)size(a) - 1, 0)); for (int i = 0; i < (int)size(res); ++i) res[i] = (i + 1) * a[i + 1]; return res; } template <class T> vector<T> primitive(const vector<T>& a) { vector<T> res(size(a) + 1); for (int i = 1; i < (int)size(res); ++i) res[i] = a[i - 1] / i; return res; } template <class T> vector<T> logarithm(const vector<T>& a) { assert(not empty(a) and a[0] == 1); auto res = primitive(derivative(a) * inverse(a)); return {begin(res), begin(res) + size(a)}; } template <unsigned M> struct modular { using m = modular; static constexpr unsigned mod = M; unsigned v; modular(long long x = 0) : v((x %= mod) < 0 ? x + mod : x) {} m operator-() const { return m() -= *this; } m& operator+=(m b) { if ((int)(v += b.v - mod) < 0) v += mod; return *this; } m& operator-=(m b) { if ((int)(v -= b.v) < 0) v += mod; return *this; } m& operator*=(m b) { v = (uint64_t)v * b.v % mod; return *this; } m& operator/=(m b) { return *this *= power(b, mod - 2); } friend m operator+(m a, m b) { return a += b; } friend m operator-(m a, m b) { return a -= b; } friend m operator*(m a, m b) { return a *= b; } friend m operator/(m a, m b) { return a /= b; } friend bool operator==(m a, m b) { return a.v == b.v; } }; using mint = modular<998244353>; vector<mint> calc(int n, int m, vector<int> b) { cin.tie(nullptr); ios::sync_with_stdio(false); vector<vector<mint>> tree(2 * n); for (int i = 0; i < n; ++i) { //int a; //cin >> a; int a = b[i]; tree[n + i] = {1, -a}; } for (int i = n; i-- > 1; ) { tree[i] = tree[2 * i] * tree[2 * i + 1]; } auto f = tree[1]; f.resize(m + 1); f = -logarithm(f); vector<mint> res; for (int k = 1; k <= m; ++k) { f[k] *= k; res.push_back(f[k]); //cout << f[k].v << " \n"[k == m]; } return res; } int main(){ int n,m; cin >> n >> m; vector<int> b; for(int i=0;i<m;i++){ b.push_back(i+1); } auto c = calc(m,n,b); mint ans = 0; mint x = 1; for(int i=0;i<n-1;i++){ x *= m; } for(int i=0;i<n;i++){ ans += c[i] * x; //cout << c[i].v << endl; x /= m; } cout << ans.v << endl; }