// これはつけてると壊れることがある (yukicoderなど) // #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; // verify: https://judge.yosupo.jp/submission/202428 // もっと早くできるらしい https://paper.dropbox.com/doc/fps-EoHXQDZxfduAB8wD1PMBW // https://qiita.com/Suu0313/items/69253873a8397323b376 vector fps_inv(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f.size()); assert(f[0].val()!=0); vector g = {(mint)1/f[0]}; vector ff = {f[0]}; for(int i=1;i<=deg;i<<=1){ // iでmod x^(2i)を計算する for(int j=ff.size();j h = convolution(g,ff); h.resize(2*i); for(mint &u:h) u = -u; h[0] += 2; g = convolution(g,h); g.resize(2*i); } g.resize(deg + 1); return g; } vector fps_derivative(vector &f){ vector ret; for(int i=1;i fps_integral(vector &f){ vector g(f.size()); for(int i=g.size() - 1;i>=1;i--){ g[i] = f[i - 1]/(mint)(i); } g[0] = 0; return g; } // get log(f) = -sum (1 - f)^n/n vector fps_log(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f[0].val()==1); vector g = convolution(fps_derivative(f),fps_inv(f,deg)); g.resize(deg + 1); return fps_integral(g); } // get exp(f) = sum f^i/i! vector fps_exp(vector f,int deg = -1){ if(deg==-1) deg = f.size() - 1; assert(f.size()); assert(f[0].val()==0); vector g = {(mint)1}; for(int i=1;i<=deg;i<<=1){ vector h(2*i); h[0] = 1; vector log_g = fps_log(g,h.size() - 1); for(int j=0;j shift(vector ff,int d){ int i,len = ff.size(); vector f1(len + 1),f2(len + 1); mint x = 1; for(i=0;i f3 = convolution(f1,f2); vector ret; for(i=len;i<2*len;i++){ ret.push_back(f3[i]*fi[i - len]); } return ret; } // input: s[0] + s[1]x + ... s[n - 1]x^n - 1 // output: (c[0] - c[1] - .. c[d])s = 0かつc[0] = 1なるcを存在すればどれか一つ // O(n^2)-time // copied from: https://nyaannyaan.github.io/library/fps/berlekamp-massey.hpp // verified: https://judge.yosupo.jp/submission/199848 // algorithmの気持ち // deg(c) = kの時に s[i] + Σ_{j vector BerlekampMassey(const vector &s) { const int N = (int)s.size(); vector b, c; b.reserve(N + 1); c.reserve(N + 1); b.push_back(mint(1)); c.push_back(mint(1)); mint y = mint(1); for(int ed = 1; ed <= N; ed++){ int l = int(c.size()), m = int(b.size()); mint x = 0; for (int i = 0; i < l; i++) x += c[i] * s[ed - l + i]; b.emplace_back(mint(0)); m++; if(x == mint(0)) continue; mint freq = x / y; if(l < m){ auto tmp = c; c.insert(begin(c), m - l, mint(0)); for (int i = 0; i < m; i++) c[m - 1 - i] -= freq * b[m - 1 - i]; b = tmp; y = x; }else{ for (int i = 0; i < m; i++) c[l - 1 - i] -= freq * b[m - 1 - i]; } } reverse(begin(c), end(c)); return c; } // BostanMori // input: P(x)/Q(x),deg(P(x)) P,vector Q,ll N){ while(N){ vector _Q(Q.size()); for(int i=0;i nP = convolution(P,_Q); vector nQ = convolution(Q,_Q); Q.resize(nQ.size()/2 + 1); for(int i=0;i sparse_pow(vector &f,int k,int N){ assert(f.size()); assert(f[0]!=0); mint iv = pw(f[0],mod - 2); vector> ff; for(int i=1;i ret(N); ret[0] = pw(f[0],k); for(int i=1;ii) break; ret[i] += ff[j].second*deg*ret[i - deg]; } ret[i] *= k; for(int j=0;ji) break; ret[i] -= ff[j].second*(i - deg)*ret[i - deg]; } ret[i] *= inv[i]; } return ret; } template // d項の漸化式で、最初のd項と漸化式cが与えられたときに、k項目を求める // cはa_i = c_0a_{i - 1} + c_1a_{i - 2} + ... と与える // verify: https://judge.yosupo.jp/submission/213985 mint kthTerm(vector &ini,vector &c,ll k){ int d = ini.size(); assert(c.size()==d); vector _c(d + 1); for(int i=0;i P = convolution(_c,ini); P.resize(d); return BostanMori(P,_c,k); } template // d項の漸化式で、最初の2d項が与えられたときに、k項目を求める (例: Fibonacchiなら前4項) mint kthTermBySequence(vector a,ll k){ vector c = BerlekampMassey(a); assert(c.size()); // cが分母の形で変えるので微調整 c.erase(c.begin()); for(mint &u:c) u *= -1; int d = c.size(); a.resize(d); return kthTerm(a,c,k); } // calc: f^e vector fps_pow(vector f,int e){ // まず[x^0]f = 1になるまでshift int mn_idx = -1,len = f.size(); for(int i=0;i g; mint c0 = f[mn_idx]; mint x = pw(c0,e); for(int i=mn_idx;i g_log = fps_log(g); for(int i=0;i g_exp = fps_exp(g_log); // mn_idx*eだけshiftする vector h(len); int shift = min(len,mn_idx*e); for(int i=0;i> n >> m; int d = m + n - n*(n - 1)/2; if(d<0 || d>n){ cout << 0 << "\n"; return 0; } vector F1(n + 1),F2(n + 1); F1[1] = 1; for(i=2;i<=n;i++) F1[i] = (mint)1/(mint)2; for(i=5;i<=n;i++) F2[i] = mint(1)/mint(2*i); vector G = fps_pow(F1,d); vector H = fps_exp(F2); // G := (x + x^2/2 + ... x^n/2)^d (lineによって1辺損するのでlineはd個ある (expであらわせる)) // H := exp(x^5/10 + x^6/12 + ...) (円順列なので1/iになるが、ひっくり返すのでさらに半分になる) vector I = convolution(G,H); mint ans = f[n]*I[n]/f[d]; cout << ans.val() << "\n"; }