Submit Info #27172

Problem Lang User Status Time Memory
Stirling Number of the First Kind cpp Jeffrey AC 993 ms 72.51 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.67 MiB
1_00 AC 3 ms 0.67 MiB
262143_00 AC 809 ms 68.60 MiB
262144_00 AC 817 ms 68.52 MiB
2_00 AC 2 ms 0.67 MiB
491519_00 AC 986 ms 72.40 MiB
499999_00 AC 993 ms 72.51 MiB
500000_00 AC 990 ms 72.51 MiB
5000_00 AC 9 ms 1.76 MiB
example_00 AC 1 ms 0.64 MiB

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <cmath> #include <complex> using namespace std; typedef long long ll; typedef pair<int, int> pii; //const int mod = 1000000007; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef vector<int> vi; typedef complex<double> C; typedef vector<double> vd; void fft(vector<C>& a) { int n = sz(a), L = 31 - __builtin_clz(n); static vector<complex<long double>> R(2, 1); static vector<C> rt(2, 1); // (^ 10% faster if double) for (static int k = 2; k < n; k *= 2) { R.resize(n); rt.resize(n); auto x = polar(1.0L, acos(-1.0L) / k); rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2]; } vi rev(n); rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2; rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]); for (int k = 1; k < n; k *= 2) for (int i = 0; i < n; i += 2 * k) rep(j,0,k) { // C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled) /// include-line auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k]; /// exclude-line C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]); /// exclude-line a[i + j + k] = a[i + j] - z; a[i + j] += z; } } vd conv(const vd& a, const vd& b) { if (a.empty() || b.empty()) return {}; vd res(sz(a) + sz(b) - 1); int L = 32 - __builtin_clz(sz(res)), n = 1 << L; vector<C> in(n), out(n); copy(all(a), begin(in)); rep(i,0,sz(b)) in[i].imag(b[i]); fft(in); for (C& x : in) x *= x; rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]); fft(out); rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n); return res; } typedef vector<ll> vl; template<int M> vl convMod(const vl &a, const vl &b) { if (a.empty() || b.empty()) return {}; vl res(sz(a) + sz(b) - 1); int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M)); vector<C> L(n), R(n), outs(n), outl(n); rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut); rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut); fft(L), fft(R); rep(i,0,n) { int j = -i & (n - 1); outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n); outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i; } fft(outl), fft(outs); rep(i,0,sz(res)) { ll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5); ll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5); res[i] = ((av % M * cut + bv) % M * cut + cv) % M; } return res; } vl solve(int l, int r) { if (l > r) return {1}; if (l == r) return {(998244353 - l) % 998244353, 1}; int m = (l + r) / 2; return convMod<998244353>(solve(l, m), solve(m + 1, r)); } int main() { ios::sync_with_stdio(false); int n; cin >> n; vl a = solve(0, n - 1); for (ll i : a) cout << i << ' '; }