結果
| 問題 | No.2351 Butterfly in Summer |
| ユーザー |
 namakoiscat
|
| 提出日時 | 2023-06-16 21:32:26 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 33,697 bytes |
| コンパイル時間 | 7,206 ms |
| コンパイル使用メモリ | 269,860 KB |
| 最終ジャッジ日時 | 2025-02-14 04:29:51 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'FPS<mint> log(const FPS<mint>&, int)':
main.cpp:1049:19: error: expected 'auto' or 'decltype(auto)' after 'integral'
1049 | FPS res = integral(diff(f) * inv(f, deg));
| ^~~~~~~~
main.cpp:1049:19: error: 'auto(x)' cannot be constrained
1049 | FPS res = integral(diff(f) * inv(f, deg));
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/*#include <bits/stdc++.h>using namespace std;int main(){*/// __builtin_popcountll() ;// multiset ;// unordered_set ;// unordered_map ;// reverse ;#include <bits/stdc++.h>using namespace std;/*#include<boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;typedef cpp_int cp ;*///-------型-------typedef long long ll;typedef string st ;typedef long double ld ;typedef unsigned long long ull ;using P = pair<ll,ll> ;using run = pair<char,ll> ;using Edge = tuple<ll,ll,ll> ;using AAA = tuple<ll,ll,ll,ll> ;//-------型-------//-------定数-------const ll mod0 = 1000000007;const ll mod1 = 998244353 ;const ll LINF = 1000000000000000000+2 ; //(10^18)const ld pai = acos(-1) ;const ld EPS = 1e-10 ;//-------定数-------//-------マクロ-------#define pb push_back#define ppb pop_back#define pf push_front#define ppf pop_front#define all(x) x.begin(), x.end()#define rep(i,a,n) for (ll i = a; i <= (n); ++i)#define rrep(i,a,b,c) for (ll i = a ; i <= (b) ; i += c)#define ketu(i,a,n) for (ll i = a; i >= (n); --i)#define re return 0;#define fore(i,a) for(auto &i:a)#define V vector#define fi first#define se second#define C cout#define E "\n";#define EE endl;//-------マクロ-------//-------テンプレ文字列-------st zz = "abcdefghijklmnopqrstuvwxyz" ;st ZZ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;st tintin = "%" ;st Y = "Yes" ;st YY = "No" ;st KU = " " ;//-------テンプレ文字列-------void chmin(ll& x ,ll y){x = min(x,y) ;}void chmax(ll& x ,ll y){x = max(x,y) ;}ll max_element(V<ll> &A){ll res = *max_element(all(A)) ;return res ;}ll max_element_index(V<ll> &A){ll res = max_element(all(A)) - A.begin() ;return res ;}ll min_element(V<ll> &A){ll res = *min_element(all(A)) ;return res ;}ll min_element_index(V<ll> &A){ll res = min_element(all(A)) - A.begin() ;return res ;}vector<ll> Y4 = {0,1,0,-1} ;vector<ll> X4 = {1,0,-1,0} ;vector<ll> Y8 = {0,1,1,1,0,-1,-1,-1} ;vector<ll> X8 = {1,1,0,-1,-1,-1,0,1} ;template<class T> T pow_mod(T A, T N, T M) {T res = 1 % M;A %= M;while (N) {if (N & 1) res = (res * A) % M;A = (A * A) % M;N >>= 1;}return res;}// Miller-Rabin 素数判定bool nis(ll N) {if (N <= 1) return false;if (N == 2) return true;if (N == 3) return true ;if (N == 5) return true ;if (N == 7) return true ;if (N == 11) return true ;if (N % 2 == 0 || N % 3 == 0 || N % 5 == 0 || N % 7 == 0 || N % 11 == 0 ) return false ;vector<ll> A = {2, 325, 9375, 28178, 450775,9780504, 1795265022};ll s = 0, d = N - 1;while (d % 2 == 0) {++s;d >>= 1;}fore(a,A) {if (a % N == 0) return true;ll t, x = pow_mod<__int128_t>(a, d, N);if (x != 1) {for (t = 0; t < s; ++t) {if (x == N - 1) break;x = __int128_t(x) * x % N;}if (t == s) return false;}}return true;}// UF.initはいっかいだけならいいけど、二回目以降はrepで初期化vector<ll> par;class UnionFind {public:// サイズをＧＥＴ！void init(ll sz) {par.resize(sz,-1);}// 各連結成分の一番上を返すll root(ll x) {if (par[x] < 0) return x;return par[x] = root(par[x]);}// 結合作業bool unite(ll x, ll y) {x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x,y);par[x] += par[y];par[y] = x;return true;}// 同じグループか判定bool same(ll x, ll y) { return root(x) == root(y);}// グループのサイズをＧＥＴ！ll size(ll x) { return -par[root(x)];}};UnionFind UF ;vector<ll> enumdiv(ll n) {vector<ll> S;for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.pb(i); if (i*i != n) S.pb(n / i); }sort(S.begin(), S.end());return S;}template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;template<typename T> using max_priority_queue = priority_queue<T, vector<T>, less<T>> ;// 使用例 min_priority_queue<ll (ここは型)> Q ;vector<pair<long long, long long>> prime_factorize(long long N){vector<pair<long long, long long>> res;for(long long a = 2; a * a <= N; ++a){if(N % a != 0) continue;long long ex = 0;while(N % a == 0) ++ex, N /= a;res.push_back({a,ex});}if(N != 1) res.push_back({N,1});return res;}ll binpower(ll a, ll b,ll c) {if(!b) return 1 ;a %= c ;ll d = binpower(a,b/2,c) ;(d *= d) %= c ;if(b%2) (d *= a) %= c ;return d ;}template<typename T>V<T> sr(V<T> A){sort(all(A)) ;reverse(all(A)) ;return A ;}map<ll,ll> Compression(V<ll> A){sort(all(A)) ;A.erase(unique(all(A)),A.end()) ;map<ll,ll> res ;ll index = 0 ;fore(u,A){res[u] = index ;index ++ ;}return res ;}V<ll> sort_erase_unique(V<ll> &A){sort(all(A)) ;A.erase(unique(all(A)),A.end()) ;return A ;}struct sqrt_machine{V<ll> A ;const ll M = 1000000 ;void init(){A.pb(-1) ;rep(i,1,M){A.pb(i*i) ;}A.pb(LINF) ;}bool scan(ll a){ll pos = lower_bound(all(A),a) - A.begin() ;if(A[pos] == -1 || A[pos] == LINF || A[pos] != a)return false ;return true ;}};sqrt_machine SM ;ll a_b(V<ll> A,ll a,ll b){ll res = 0 ;res += upper_bound(all(A),b) - lower_bound(all(A),a) ;return res ;}struct era{ll check[10000010] ;void init(){rep(i,2,10000000){if(check[i] == 0){for(ll j = i + i ;j <= 10000000 ; j += i){check[j] ++ ;}}}}bool look(ll x){if(x == 1)return false ;if(check[x] == 0)return true ;else return false ;}ll enu_count(ll x){if(x == 1)return 1 ;if(check[x] == 0)return 1 ;return check[x] ;}};era era ;st _10_to_2(ll x){st abc = "" ;if(x == 0){return "0" ;}while(x > 0){abc = char(x%2 + '0') + abc ;x /= 2 ;}return abc ;}ll _2_to_10(st op){ll abc = 0 ;ll K = op.size() ;for(ll i = 0 ;i < K ;i++){abc = abc * 2 + ll(op[i] - '0') ;}return abc ;}ll powpow(ll A , ll B){ll res = 1 ;rep(i,1,B){res *= A ;}return res ;}V<run> Run_Length_Encoding(st S){ll N = S.size() ;V<pair<char,ll>> A ;ll count = 0 ;char cc ;bool RLEflag = false ;if(N == 1){A.pb({S[0],1}) ;RLEflag = true ;}rep(i,0,N-1){if(RLEflag == true)break ;if(i == 0){cc = S[i] ;count = 1 ;continue ;}if(i == N-1){if(S[i] == cc){A.pb({cc,count + 1}) ;}else{A.pb({cc,count}) ;A.pb({S[i],1}) ;}break ;}if(S[i] == cc){count ++ ;}else{A.pb({cc,count}) ;cc = S[i] ;count = 1 ;}}return A ;}ll kiriage(ll a , ll b){return (a + b - 1) / b ;}ll a_up(V<ll> &A , ll x){if(A[A.size()-1] < x)return -1 ;ll res = lower_bound(all(A),x) - A.begin() ;return A[res] ;}ll b_down(V<ll> &B , ll x){if(B[0] > x)return -1 ;ll res = upper_bound(all(B),x) - B.begin() ;return B[res-1] ;}ll Permutation(ll N){ll res = 1 ;rep(i,1,N)res *= i ;return res ;}V<V<ll>> Next_permutation(ll N){ll Size = Permutation(N) ;V<V<ll>> res(Size) ;V<ll> per(N) ;rep(i,0,N-1)per[i] = i ;ll count = 0 ;do{fore(u,per){res[count].pb(u) ;}count ++ ;}while(next_permutation(per.begin(),per.end()));return res ;}/*st Regex(st S, st A ,st B){return regex_replace(S,regex(A),B) ;}st erase_string(st S , st T){st ans = S.erase(S.find(T),T.length()) ;return ans ;}*/ll pow_daisyou(ll a , ll b , ll c){ll d = c%2==1 ? 1 : 2 ;ll ans = -1 ;if(powpow(a,d) == powpow(b,d))ans = 0 ;if(powpow(a,d) > powpow(b,d))ans = 1 ;else if(powpow(a,d) < powpow(b,d))ans = 2 ;return ans ;}template<typename T>void debag_1V_kaigyou(V<T> A){ll N = A.size() ;rep(i,0,N-1){C << A[i] << E}}template<typename T>void debag_1V_space(V<T> A){ll N = A.size() ;rep(i,0,N-1){C << A[i] << KU ;}C << E}template<typename T>void debag_2V(V<V<T>> A){ll N = A.size() ;ll M = A[0].size() ;rep(i,0,N-1){rep(j,0,M-1){if(A[i][j] == LINF || A[i][j] == LINF)C << "L" << KU ;else C << A[i][j] << KU ;}C << E}}void debag_pair(V<P> A){ll N = A.size() ;rep(i,0,N-1){auto [a,b] = A[i] ;C << a << KU << b << E}}void debag_Edge(V<Edge> A){ll N = A.size() ;rep(i,0,N-1){auto [a,b,c] = A[i] ;C << a << KU << b << KU << c << E}}V<P> sort_Args(int len, ...){V<ll> arr;va_list args;va_start(args, len);for (int i = 0; i < len; ++i){ll arg = va_arg(args, ll);arr.push_back(arg);}va_end(args);sort(arr.begin(), arr.end());V<P> pos ;pos.pb({0,-LINF}) ;ll index = 1 ;rep(i,0,len-1){pos.pb({index,arr[i]}) ;index ++ ;}return pos ;}ll c_c(char s){ll x = s - 'a' ;return x ;}ll C_C(char S){ll X = S - 'A' ;return X ;}// FPS (けんちょんさん)/*解説 https://drken1215.hatenablog.com/archive/category/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E5%86%AA%E7%B4%9A%E6%95%B0f *= g問題 https://atcoder.jp/contests/tdpc/tasks/tdpc_contest提出 https://atcoder.jp/contests/tdpc/submissions/42229178f /= g係数そのままだしたかったら、 mod998なら1000000 >= なら -= MODする問題 https://atcoder.jp/contests/abc245/tasks/abc245_d提出 https://atcoder.jp/contests/abc245/submissions/42229617inv問題 https://yukicoder.me/problems/no/3046提出 https://yukicoder.me/submissions/880939解説 https://drken1215.hatenablog.com/entry/2020/10/08/014500こっちはACL特に必要ない初期化 FPS f(N) ;掛け算 f * gFPS<mint> g(MAX) ;g[0] = 1 ; g[a] = 1 ;f *= g ;pow f = (x+1) で (x+1)^2がほしいならFPS<mint> ff = pow(f,2,N) ; // Nは項数か FPS<mint> ff = pow(f,2) ;log , exp , inv も同じ感じinv = 1/finv やるときは余分にサイズとっておかないとREでるFPS<mint> f(N+10) ; みたいにしないとだめBiCoefできること初期化 Bicoef<mint> bc(N) ;bc.fact(i) ===> i!bc.finv(i) ===> (1/i!)bc.com(n,k) ===> nCkbc.inv(i) ===> 1/iBostan-Mori [x^N]P(x) / Q(x) を P(x)のサイズKとしたら、O(KlogKlogN)でだすアルゴリズムP(x) はK次以下の多項式 , Q(x)はBostanMori()*/// --------------------------code----------------------------// modinttemplate<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}constexpr int getmod() const { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {if (n == 0) return 1;if (n < 0) return modpow(modinv(r), -n);auto t = modpow(r, n / 2);t = t * t;if (n & 1) t = t * r;return t;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}};namespace NTT {long long modpow(long long a, long long n, int mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, int mod) {long long b = mod, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}int calc_primitive_root(int mod) {if (mod == 2) return 1;if (mod == 167772161) return 3;if (mod == 469762049) return 3;if (mod == 754974721) return 11;if (mod == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;long long x = (mod - 1) / 2;while (x % 2 == 0) x /= 2;for (long long i = 3; i * i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) x /= i;}}if (x > 1) divs[cnt++] = x;for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (modpow(g, (mod - 1) / divs[i], mod) == 1) {ok = false;break;}}if (ok) return g;}}int get_fft_size(int N, int M) {int size_a = 1, size_b = 1;while (size_a < N) size_a <<= 1;while (size_b < M) size_b <<= 1;return max(size_a, size_b) << 1;}// number-theoretic transformtemplate<class mint> void trans(vector<mint>& v, bool inv = false) {if (v.empty()) return;int N = (int)v.size();int MOD = v[0].getmod();int PR = calc_primitive_root(MOD);static bool first = true;static vector<long long> vbw(30), vibw(30);if (first) {first = false;for (int k = 0; k < 30; ++k) {vbw[k] = modpow(PR, (MOD - 1) >> (k + 1), MOD);vibw[k] = modinv(vbw[k], MOD);}}for (int i = 0, j = 1; j < N - 1; j++) {for (int k = N >> 1; k > (i ^= k); k >>= 1);if (i > j) swap(v[i], v[j]);}for (int k = 0, t = 2; t <= N; ++k, t <<= 1) {long long bw = vbw[k];if (inv) bw = vibw[k];for (int i = 0; i < N; i += t) {mint w = 1;for (int j = 0; j < t/2; ++j) {int j1 = i + j, j2 = i + j + t/2;mint c1 = v[j1], c2 = v[j2] * w;v[j1] = c1 + c2;v[j2] = c1 - c2;w *= bw;}}}if (inv) {long long invN = modinv(N, MOD);for (int i = 0; i < N; ++i) v[i] = v[i] * invN;}}// for garnerstatic constexpr int MOD0 = 754974721;static constexpr int MOD1 = 167772161;static constexpr int MOD2 = 469762049;using mint0 = Fp<MOD0>;using mint1 = Fp<MOD1>;using mint2 = Fp<MOD2>;static const mint1 imod0 = 95869806; // modinv(MOD0, MOD1);static const mint2 imod1 = 104391568; // modinv(MOD1, MOD2);static const mint2 imod01 = 187290749; // imod1 / MOD0;// small case (T = mint, long long)template<class T> vector<T> naive_mul(const vector<T>& A, const vector<T>& B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();vector<T> res(N + M - 1);for (int i = 0; i < N; ++i)for (int j = 0; j < M; ++j)res[i + j] += A[i] * B[j];return res;}// minttemplate<class mint> vector<mint> mul(const vector<mint>& A, const vector<mint>& B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();if (min(N, M) < 30) return naive_mul(A, B);int MOD = A[0].getmod();int size_fft = get_fft_size(N, M);if (MOD == 998244353) {vector<mint> a(size_fft), b(size_fft), c(size_fft);for (int i = 0; i < N; ++i) a[i] = A[i];for (int i = 0; i < M; ++i) b[i] = B[i];trans(a), trans(b);vector<mint> res(size_fft);for (int i = 0; i < size_fft; ++i) res[i] = a[i] * b[i];trans(res, true);res.resize(N + M - 1);return res;}vector<mint0> a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0);vector<mint1> a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0);vector<mint2> a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0);for (int i = 0; i < N; ++i)a0[i] = A[i].val, a1[i] = A[i].val, a2[i] = A[i].val;for (int i = 0; i < M; ++i)b0[i] = B[i].val, b1[i] = B[i].val, b2[i] = B[i].val;trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2);for (int i = 0; i < size_fft; ++i) {c0[i] = a0[i] * b0[i];c1[i] = a1[i] * b1[i];c2[i] = a2[i] * b2[i];}trans(c0, true), trans(c1, true), trans(c2, true);static const mint mod0 = MOD0, mod01 = mod0 * MOD1;vector<mint> res(N + M - 1);for (int i = 0; i < N + M - 1; ++i) {int y0 = c0[i].val;int y1 = (imod0 * (c1[i] - y0)).val;int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val;res[i] = mod01 * y2 + mod0 * y1 + y0;}return res;}// long longvector<long long> mul_ll(const vector<long long>& A, const vector<long long>& B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();if (min(N, M) < 30) return naive_mul(A, B);int size_fft = get_fft_size(N, M);vector<mint0> a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0);vector<mint1> a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0);vector<mint2> a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0);for (int i = 0; i < N; ++i)a0[i] = A[i], a1[i] = A[i], a2[i] = A[i];for (int i = 0; i < M; ++i)b0[i] = B[i], b1[i] = B[i], b2[i] = B[i];trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2);for (int i = 0; i < size_fft; ++i) {c0[i] = a0[i] * b0[i];c1[i] = a1[i] * b1[i];c2[i] = a2[i] * b2[i];}trans(c0, true), trans(c1, true), trans(c2, true);static const long long mod0 = MOD0, mod01 = mod0 * MOD1;vector<long long> res(N + M - 1);for (int i = 0; i < N + M - 1; ++i) {int y0 = c0[i].val;int y1 = (imod0 * (c1[i] - y0)).val;int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val;res[i] = mod01 * y2 + mod0 * y1 + y0;}return res;}};// Binomial coefficienttemplate<class T> struct BiCoef {vector<T> fact_, inv_, finv_;constexpr BiCoef() {}constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n);}constexpr void init(int n) noexcept {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].getmod();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];}}constexpr T com(int n, int k) const noexcept {if (n < k || n < 0 || k < 0) return 0;return fact_[n] * finv_[k] * finv_[n-k];}constexpr T fact(int n) const noexcept {if (n < 0) return 0;return fact_[n];}constexpr T inv(int n) const noexcept {if (n < 0) return 0;return inv_[n];}constexpr T finv(int n) const noexcept {if (n < 0) return 0;return finv_[n];}};// Formal Power Seriestemplate <typename mint> struct FPS : vector<mint> {using vector<mint>::vector;// constructorFPS(const vector<mint>& r) : vector<mint>(r) {}// core operatorinline FPS pre(int siz) const {return FPS(begin(*this), begin(*this) + min((int)this->size(), siz));}inline FPS rev() const {FPS res = *this;reverse(begin(res), end(res));return res;}inline FPS& normalize() {while (!this->empty() && this->back() == 0) this->pop_back();return *this;}// basic operatorinline FPS operator - () const noexcept {FPS res = (*this);for (int i = 0; i < (int)res.size(); ++i) res[i] = -res[i];return res;}inline FPS operator + (const mint& v) const { return FPS(*this) += v; }inline FPS operator + (const FPS& r) const { return FPS(*this) += r; }inline FPS operator - (const mint& v) const { return FPS(*this) -= v; }inline FPS operator - (const FPS& r) const { return FPS(*this) -= r; }inline FPS operator * (const mint& v) const { return FPS(*this) *= v; }inline FPS operator * (const FPS& r) const { return FPS(*this) *= r; }inline FPS operator / (const mint& v) const { return FPS(*this) /= v; }inline FPS operator << (int x) const { return FPS(*this) <<= x; }inline FPS operator >> (int x) const { return FPS(*this) >>= x; }inline FPS& operator += (const mint& v) {if (this->empty()) this->resize(1);(*this)[0] += v;return *this;}inline FPS& operator += (const FPS& 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->normalize();}inline FPS& operator -= (const mint& v) {if (this->empty()) this->resize(1);(*this)[0] -= v;return *this;}inline FPS& operator -= (const FPS& 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->normalize();}inline FPS& operator *= (const mint& v) {for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= v;return *this;}inline FPS& operator *= (const FPS& r) {return *this = NTT::mul((*this), r);}inline FPS& operator /= (const mint& v) {assert(v != 0);mint iv = modinv(v);for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= iv;return *this;}inline FPS& operator <<= (int x) {FPS res(x, 0);res.insert(res.end(), begin(*this), end(*this));return *this = res;}inline FPS& operator >>= (int x) {FPS res;res.insert(res.end(), begin(*this) + x, end(*this));return *this = res;}inline mint eval(const mint& v){mint res = 0;for (int i = (int)this->size()-1; i >= 0; --i) {res *= v;res += (*this)[i];}return res;}inline friend FPS gcd(const FPS& f, const FPS& g) {if (g.empty()) return f;return gcd(g, f % g);}// advanced operation// df/dxinline friend FPS diff(const FPS& f) {int n = (int)f.size();FPS res(n-1);for (int i = 1; i < n; ++i) res[i-1] = f[i] * i;return res;}// \int f dxinline friend FPS integral(const FPS& f) {int n = (int)f.size();FPS res(n+1, 0);for (int i = 0; i < n; ++i) res[i+1] = f[i] / (i+1);return res;}// inv(f), f[0] must not be 0inline friend FPS inv(const FPS& f, int deg) {assert(f[0] != 0);if (deg < 0) deg = (int)f.size();FPS res({mint(1) / f[0]});for (int i = 1; i < deg; i <<= 1) {res = (res + res - res * res * f.pre(i << 1)).pre(i << 1);}res.resize(deg);return res;}inline friend FPS inv(const FPS& f) {return inv(f, f.size());}// division, r must be normalized (r.back() must not be 0)inline FPS& operator /= (const FPS& r) {assert(!r.empty());assert(r.back() != 0);this->normalize();if (this->size() < r.size()) {this->clear();return *this;}int need = (int)this->size() - (int)r.size() + 1;*this = ((*this).rev().pre(need) * inv(r.rev(), need)).pre(need).rev();return *this;}inline FPS& operator %= (const FPS &r) {assert(!r.empty());assert(r.back() != 0);this->normalize();FPS q = (*this) / r;return *this -= q * r;}inline FPS operator / (const FPS& r) const { return FPS(*this) /= r; }inline FPS operator % (const FPS& r) const { return FPS(*this) %= r; }// log(f) = \int f'/f dx, f[0] must be 1inline friend FPS log(const FPS& f, int deg) {assert(f[0] == 1);FPS res = integral(diff(f) * inv(f, deg));res.resize(deg);return res;}inline friend FPS log(const FPS& f) {return log(f, f.size());}// exp(f), f[0] must be 0inline friend FPS exp(const FPS& f, int deg) {assert(f[0] == 0);FPS res(1, 1);for (int i = 1; i < deg; i <<= 1) {res = res * (f.pre(i<<1) - log(res, i<<1) + 1).pre(i<<1);}res.resize(deg);return res;}inline friend FPS exp(const FPS& f) {return exp(f, f.size());}// pow(f) = exp(e * log f)inline friend FPS pow(const FPS& f, long long e, int deg) {long long i = 0;while (i < (int)f.size() && f[i] == 0) ++i;if (i == (int)f.size()) return FPS(deg, 0);if (i * e >= deg) return FPS(deg, 0);mint k = f[i];FPS res = exp(log((f >> i) / k, deg) * e, deg) * modpow(k, e) << (e * i);res.resize(deg);return res;}inline friend FPS pow(const FPS& f, long long e) {return pow(f, e, f.size());}// sqrt(f), f[0] must be 1inline friend FPS sqrt_base(const FPS& f, int deg) {assert(f[0] == 1);mint inv2 = mint(1) / 2;FPS res(1, 1);for (int i = 1; i < deg; i <<= 1) {res = (res + f.pre(i << 1) * inv(res, i << 1)).pre(i << 1);for (mint& x : res) x *= inv2;}res.resize(deg);return res;}inline friend FPS sqrt_base(const FPS& f) {return sqrt_base(f, f.size());}};////////////////////////////////////////// FPS algorithms////////////////////////////////////////// Bostan-Mori// find [x^N] P(x)/Q(x), O(K log K log N)// deg(Q(x)) = K, deg(P(x)) < Ktemplate <typename mint> mint BostanMori(const FPS<mint> &P, const FPS<mint> &Q, long long N) {assert(!P.empty() && !Q.empty());if (N == 0 || Q.size() == 1) return P[0] / Q[0];int qdeg = (int)Q.size();FPS<mint> P2{P}, minusQ{Q};P2.resize(qdeg - 1);for (int i = 1; i < (int)Q.size(); i += 2) minusQ[i] = -minusQ[i];P2 *= minusQ;FPS<mint> Q2 = Q * minusQ;FPS<mint> S(qdeg - 1), T(qdeg);for (int i = 0; i < (int)S.size(); ++i) {S[i] = (N % 2 == 0 ? P2[i * 2] : P2[i * 2 + 1]);}for (int i = 0; i < (int)T.size(); ++i) {T[i] = Q2[i * 2];}return BostanMori(S, T, N >> 1);}// const int MOD = mod0 ;const int MOD = mod1 ;using mint = Fp<MOD> ;// --------------------------code----------------------------int main(void){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// SM.init() ;// era.init() ;// max_element(V<ll> A) Aの最大値を返す// max_element_index(V<ll> A) Aの最大値のindex// min_element(V<ll> A) Aの最小値を返す// min_element_index(V<ll> A) Aの最小値のindex// gcd(ll a , ll b) gcd(a,b) ;// lcm(ll a ,ll b ) lcm// nis(ll a) 素数判定 素数ならtrue// UF UF.init(ll N) ; UF.root(i) ; UF.unite(a,b) ; UF.same(a,b) ; UF.size(i) ;// enumdiv(ll a )約数列挙// prime_factorize(ll p) aのb乗のかたちででてくる 配列で受け取る// binpower(a,b,c) aのb条 をｃでわったやつをO(logb) ぐらいでだしてくれるやつ// sr(V<ll> A) 配列を入れたら、sort --→ reverse して返してくれる関数 受け取りは auto とかで// sort_erase_unique(V<ll> A) sortしてeraseしてuniqueする関数// Compression(V<ll> A) 座圧したmapを返す関数// SM.scan(ll a) で 平方数ならtrue が返ってくる。 範囲は √10^6まで SM.init() 必ず起動する。// a_b(A,a,b) [a,b]の個数 ---→ upper_bound(all(A),b) - lower_bound(all(A),a) ;// era.look(ll a) --→ true 素数 / era.enu_count(ll a) --→ 素因数の個数 1は1 、素数も1 その他はそのまんま 範囲は10^7まで// _10_to_2(ll x) 10進数を二進数にして返す。文字列で出力する事に注意 ll --→ st// _2_to_10(st a) 2進数を10進数にして返す。 st --→ ll// powpow(ll a,ll b) a^b を返す// Run_Length_Encoding(st S) ランレングス圧縮して配列を返す pair<char,ll>// Regex(st S, st A , st B) SのAをBに変えた文字列を返す 使う場合は消す// erase_string(st S , st T) Sの中のTを消す// kiriage(ll a , ll b) a 割られる数 b 割る数// a_up(V<ll> A , ll x) sort済み配列でｘ以上の最小値を返す。ない場合、-1を返す.// b_down(V<ll> B , ll x)sort済み配列でx以下で最大値を返す。ない場合 -1を返す。// Permutation(ll N) N!の値を返す。20までならオーバーフローしない。// V<V<ll>> Next_permutation(ll N) next_permutationした配列の集合を返す.// pow_daisyou(ll a, ll b , ll c )a^cとb^cを比較する 0 => 同値 1 => a側 2=> ｂ側// debag_1V_kaigyou(V<ll> A) 一次元配列の中身を改行区切りで出力する// debag_1V_space(V<ll> A) 一次元配列Aの中身をspace区切りで出力する// debag_2V(V<V<ll>> A) 2次元配列Aの中身を返す関数// debag_pair(V<P> A) pair型配列の中身を出力する// debag_Edge(V<Edge> A) Edge型配列の中身を出力する// V<P> sort_Args(len,a,b,c) 個数を指定して、その個数だけ変数を渡し、昇順にして返す。1-indexになってる。// c_c 小文字charを数字に変換// C_C 大文字charを数字に変換// (double)clock()/CLOCKS_PER_SEC>1.987// multisetで1つだけ要素消したかったら、 A.erase(A.find(x)) ;とする。// mod0 --→ 1000000007 mod1 --→ 998244353// 座圧した後、size変わることに注意。二回やらかしてますll N,K ;cin >> N >> K ;mint p = (K-1) * N * K ;mint q = mint(binpower(K,N,mod1)) ;mint ans = p / q ;C << ans.val << E// if(dx < 0 || dy < 0 || dx >= W || dy >= H) continue ;// C << fixed << setprecision(10) << // 勝手に四捨五入してくれてるから安心してre}