Submit Info #57444

Problem Lang User Status Time Memory
Stirling Number of the First Kind cpp leaf1415 AC 1017 ms 34.19 MiB

ケース詳細
Name Status Time Memory
0_00 AC 7 ms 4.71 MiB
1_00 AC 7 ms 4.71 MiB
262143_00 AC 669 ms 21.84 MiB
262144_00 AC 413 ms 17.66 MiB
2_00 AC 8 ms 4.72 MiB
491519_00 AC 1017 ms 34.04 MiB
499999_00 AC 1012 ms 34.19 MiB
500000_00 AC 479 ms 20.27 MiB
5000_00 AC 12 ms 4.96 MiB
example_00 AC 7 ms 4.71 MiB

#include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <ctime> #include <cstdlib> #include <cassert> #include <vector> #include <list> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <string> #include <algorithm> #include <utility> #include <complex> #include <unordered_set> #include <unordered_map> #define rep(x, s, t) for(ll x = (s); (x) <= (t); (x)++) #define per(x, s, t) for(ll x = (s); (x) >= (t); (x)--) #define reps(x, s) for(ll x = 0; (x) < (ll)(s).size(); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define sz(x) ((ll)(x).size()) #define ceil(x, y) (((x)+(y)-1) / (y)) #define all(x) (x).begin(),(x).end() #define outl(...) dump_func(__VA_ARGS__) #define outf(x) cout << fixed << setprecision(16) << (x) << endl #define inf 1e18 const double PI = 3.1415926535897932384626433; using namespace std; typedef long long llint; typedef long long ll; typedef pair<ll, ll> P; struct edge{ ll to, cost; edge(){} edge(ll a, ll b){ to = a, cost = b;} }; const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; //const int mod = 1000000007; const int mod = 998244353; struct mint{ int x; mint(ll y = 0){x = y; if(x < 0 || x >= mod) x = (x%mod+mod)%mod;} mint(const mint &ope) {x = ope.x;} mint operator-(){return mint(-x);} mint operator+(const mint &ope){return mint(x) += ope;} mint operator-(const mint &ope){return mint(x) -= ope;} mint operator*(const mint &ope){return mint(x) *= ope;} mint operator/(const mint &ope){return mint(x) /= ope;} mint& operator+=(const mint &ope){ x += ope.x; if(x >= mod) x -= mod; return *this; } mint& operator-=(const mint &ope){ x += mod - ope.x; if(x >= mod) x -= mod; return *this; } mint& operator*=(const mint &ope){ ll tmp = x; tmp *= ope.x, tmp %= mod; x = tmp; return *this; } mint& operator/=(const mint &ope){ ll n = mod-2; mint mul = ope; while(n){ if(n & 1) *this *= mul; mul *= mul; n >>= 1; } return *this; } mint inverse(){return mint(1) / *this;} bool operator ==(const mint &ope){return x == ope.x;} bool operator !=(const mint &ope){return x != ope.x;} bool operator <(const mint &ope){return x < ope.x;} }; mint modpow(mint a, ll n){ if(n == 0) return mint(1); if(n % 2) return a * modpow(a, n-1); else return modpow(a*a, n/2); } istream& operator >>(istream &is, mint &ope){ ll t; is >> t, ope.x = t; return is; } ostream& operator <<(ostream &os, mint &ope){return os << ope.x;} ostream& operator <<(ostream &os, const mint &ope){return os << ope.x;} vector<mint> fact, fact_inv; void make_fact(int n){ fact.resize(n+1), fact_inv.resize(n+1); fact[0] = mint(1); rep(i, 1, n) fact[i] = fact[i-1] * mint(i); fact_inv[n] = fact[n].inverse(); per(i, n-1, 0) fact_inv[i] = fact_inv[i+1] * mint(i+1); } mint comb(int n, int k){ if(n < 0 || k < 0 || n < k) return mint(0); return fact[n] * fact_inv[k] * fact_inv[n-k];} mint perm(int n, int k){ return comb(n, k) * fact[k]; } vector<int> prime, pvec; void make_prime(int n){ prime.resize(n+1); rep(i, 2, n){ if(prime[i]) continue; for(int j = i; j <= n; j+=i) prime[j] = i; } rep(i, 2, n) if(prime[i] == i) pvec.push_back(i); } bool exceed(ll x, ll y, ll m){return x >= m / y + 1;} void mark(){ cout << "*" << endl; } void yes(){ cout << "YES" << endl; } void no(){ cout << "NO" << endl; } ll sgn(ll x){ if(x > 0) return 1; if(x < 0) return -1; return 0;} ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a%b);} ll lcm(ll a, ll b){return a/gcd(a, b)*b;} ll digitnum(ll x, ll b = 10){ll ret = 0; for(; x; x /= b) ret++; return ret;} ll digitsum(ll x, ll b = 10){ll ret = 0; for(; x; x /= b) ret += x % b; return ret;} string lltos(ll x){string ret; for(;x;x/=10) ret += x % 10 + '0'; reverse(ret.begin(), ret.end()); return ret;} ll stoll(string &s){ll ret = 0; for(auto c : s) ret *= 10, ret += c - '0'; return ret;} template<typename T> void uniq(T &vec){ sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());} template<class S, class T> pair<S, T>& operator+=(pair<S,T> &s, const pair<S,T> &t){ s.first += t.first, s.second += t.second; return s; } template<class S, class T> pair<S, T>& operator-=(pair<S,T> &s, const pair<S,T> &t){ s.first -= t.first, s.second -= t.second; return s; } template<class S, class T> pair<S, T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second); } template<class S, class T> pair<S, T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second); } template<typename T> ostream& operator << (ostream& os, vector<T>& vec) { for(int i = 0; i < vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template<typename T> ostream& operator << (ostream& os, deque<T>& deq) { for(int i = 0; i < deq.size(); i++) os << deq[i] << (i + 1 == deq.size() ? "" : " "); return os; } template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U>& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) { for(typename map<T, U>::iterator itr = map_var.begin(); itr != map_var.end(); itr++) { os << "(" << itr->first << ", " << itr->second << ")"; itr++; if(itr != map_var.end()) os << ","; itr--; } return os; } template<typename T> ostream& operator << (ostream& os, set<T>& set_var) { for(typename set<T>::iterator itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if(itr != set_var.end()) os << " "; itr--; } return os; } template<typename T> ostream& operator << (ostream& os, multiset<T>& set_var) { for(typename multiset<T>::iterator itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if(itr != set_var.end()) os << " "; itr--; } return os; } template<typename T> void outa(T a[], ll s, ll t){rep(i, s, t){ cout << a[i]; if(i < t) cout << " ";}cout << endl;} void dump_func(){cout << endl;} template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) { cout << head; if(sizeof...(Tail) > 0) cout << " "; dump_func(std::move(tail)...); } struct NTT_Convolution{ NTT_Convolution(){}; static int rev(int x, int n){ int ret = 0; for(int i = 0; i < n; i++) ret <<= 1, ret |= (x>>i) & 1; return ret; } static void DFT(vector<mint> &f, vector<mint> &F, int n, mint root, bool inv = false) { int N = 1<<n; F.resize(N); for(int i = 0; i < N; i++) F[rev(i, n)] = f[i]; if(inv) root = root.inverse(); mint a, b, x, z; for(int i = 0; i < n; i++){ int l = 1<<i; z = modpow(root, 1<<(n-(i+1))); for(int j = 0; j < N; j+=l*2){ x = 1; for(int k = j; k < j+l; k++){ a = F[k], b = F[k+l] * x; F[k] = a + b, F[k+l] = a - b, x *= z; } } } if(inv){ mint Ninv = mint(N).inverse(); for(int i = 0; i < N; i++) F[i] *= Ninv; } } static void conv(vector<mint> f, vector<mint> g, vector<mint> &dest) { ll logf = 0, logg = 0, len = f.size() + g.size(); for(int i = f.size(); i; i /= 2) logf++; for(int i = g.size(); i; i /= 2) logg++; ll n = max(logf, logg)+1, N = 1<<n; f.resize(N), g.resize(N); mint root = modpow(mint(3), 119 * (1<<23-n)); vector<mint> F, G; DFT(f, F, n, root), DFT(g, G, n, root); for(int i = 0; i < N; i++) F[i] *= G[i]; DFT(F, f, n, root, true); f.resize(len-1); dest = f; } }; struct FPS{ static void inverse(vector<mint> f, int n, vector<mint> &dest) //required: f[0] != 0 { int logn = digitnum(n, 2); while(f.size() < (1<<logn)) f.push_back(mint(0)); vector<mint> fvec, gvec, ngvec; fvec.push_back(f[0]), gvec.push_back(f[0].inverse()); for(int i = 1; i <= logn; i++){ while(fvec.size() < (1<<i)) fvec.push_back(f[fvec.size()]); NTT_Convolution::conv(fvec, gvec, ngvec), ngvec.resize(1<<i); for(auto &x : ngvec) x = -x; ngvec[0] += mint(2); NTT_Convolution::conv(gvec, ngvec, ngvec), ngvec.resize(1<<i); swap(gvec, ngvec); } dest = gvec, dest.resize(n); } static void derivative(vector<mint> f, vector<mint> &dest) { dest.resize(f.size()-1); if(dest.size() == 0){ dest.push_back(mint(0)); return; } for(int i = 0; i < dest.size(); i++) dest[i] = f[i+1] * mint(i+1); } static void integral(vector<mint> f, vector<mint> &dest) { dest.resize(f.size()+1); dest[0] = mint(0); for(int i = 0; i < f.size(); i++) dest[i+1] = f[i] / mint(i+1); } static void log(vector<mint> f, int n, vector<mint> &dest) //required: f[0] == 1 { vector<mint> df; FPS::derivative(f, df), FPS::inverse(f, n, f); NTT_Convolution::conv(df, f, f); FPS::integral(f, dest); dest.resize(n); } static void exp(vector<mint> f, int n, vector<mint> &dest) //required: f[0] == 0 { int logn = digitnum(n, 2); while(f.size() < (1<<logn)) f.push_back(mint(0)); vector<mint> fvec, gvec, ngvec; fvec.push_back(f[0]), gvec.push_back(mint(1)); for(int i = 1; i <= logn; i++){ while(fvec.size() < (1<<i)) fvec.push_back(f[fvec.size()]); log(gvec, (1<<i), ngvec), ngvec.resize(1<<i); for(int j = 0; j < (1<<i); j++) ngvec[j] = fvec[j] - ngvec[j]; ngvec[0] += mint(1); NTT_Convolution::conv(gvec, ngvec, ngvec); ngvec.resize(1<<i); swap(gvec, ngvec); } dest = gvec, dest.resize(n); } static void shift(vector<mint> f, mint c, vector<mint> &dest) //階乗の前計算が必要 { int n = f.size(); dest.clear(), dest.resize(n); vector<mint> avec(n), bvec(n); for(int i = 0; i < n; i++){ avec[i] = f[i] * fact[i]; bvec[i] = modpow(c, n-1-i) * fact_inv[n-1-i]; } NTT_Convolution::conv(avec, bvec, dest); dest.erase(dest.begin(), dest.begin()+(n-1)); for(int i = 0; i < n; i++) dest[i] *= fact_inv[i]; } }; void stirling_number_1st(vector<mint> &dest, int n) //S(n, 0), S(n, 1) ... S(n, n)を計算する。階乗の前計算が必要 { dest.clear(); dest.push_back(1); int logn = digitnum(n, 2), deg = 0; for(int i = logn-1; i >= 0; i--){ vector<mint> tmp = dest; FPS::shift(tmp, mint(deg), tmp); NTT_Convolution::conv(dest, tmp, dest); deg *= 2; if(n & (1<<i)){ FPS::shift(dest, mint(1), dest); dest.insert(dest.begin(), mint(0)); deg++; } } } ll n; int main(void) { ios::sync_with_stdio(0); cin.tie(0); make_fact(1<<19); cin >> n; vector<mint> ans; stirling_number_1st(ans, n); reps(i, ans){ if((n+i) % 2) cout << -ans[i] << " "; else cout << ans[i] << " "; } cout << endl; return 0; }