Submit Info #39199

Problem Lang User Status Time Memory
Log of Formal Power Series cpp catupper AC 1914 ms 65.97 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.62 MiB
max_all_zero_00 AC 1439 ms 65.97 MiB
max_random_00 AC 1868 ms 65.86 MiB
max_random_01 AC 1914 ms 65.86 MiB
max_random_02 AC 1851 ms 65.92 MiB
max_random_03 AC 1842 ms 65.86 MiB
max_random_04 AC 1898 ms 65.97 MiB
near_262144_00 AC 794 ms 36.05 MiB
near_262144_01 AC 779 ms 36.00 MiB
near_262144_02 AC 1740 ms 64.09 MiB
random_00 AC 1774 ms 65.12 MiB
random_01 AC 1836 ms 65.68 MiB
random_02 AC 152 ms 9.35 MiB
random_03 AC 1826 ms 65.35 MiB
random_04 AC 1768 ms 64.23 MiB
small_degree_00 AC 1 ms 0.67 MiB
small_degree_01 AC 1 ms 0.67 MiB
small_degree_02 AC 1 ms 0.67 MiB
small_degree_03 AC 1 ms 0.66 MiB
small_degree_04 AC 1 ms 0.61 MiB
small_degree_05 AC 1 ms 0.66 MiB
small_degree_06 AC 1 ms 0.66 MiB
small_degree_07 AC 1 ms 0.66 MiB
small_degree_08 AC 1 ms 0.67 MiB
small_degree_09 AC 1 ms 0.67 MiB

#include<iostream> #include<algorithm> #include<vector> #include<map> using namespace std; using Int = long long int; const Int MOD = 998244353; template<int MOD> struct modint{ int val; modint(Int v = 0){ if(0 <= v && v < MOD)val = v; else{ val = v % MOD; if(val < 0)val += MOD; } } modint operator*(modint &other){ return modint(Int(val) * other.val); } modint operator*(modint &&other){ return modint(Int(val) * other.val); } void operator*=(modint &other){ *this = *this * other; } void operator*=(modint &&other){ *this = *this * other; } modint operator+(modint &other){ auto tmp = val + other.val; if(tmp > MOD)tmp -= MOD; return modint(tmp); } modint operator+(modint &&other){ auto tmp = val + other.val; if(tmp > MOD)tmp -= MOD; return modint(tmp); } void operator+=(modint &other){ val += other.val; if(val >= MOD)val -= MOD; } void operator+=(modint &&other){ val += other.val; if(val >= MOD)val -= MOD; } modint operator-(modint &other){ auto tmp = val - other.val; if(tmp < 0)tmp += MOD; return modint(tmp); } modint operator-(modint &&other){ auto tmp = val - other.val; if(tmp < 0)tmp += MOD; return modint(tmp); } void operator-=(modint &other){ val -= other.val; if(val < 0)val += MOD; } void operator-=(modint &&other){ val -= other.val; if(val < 0)val += MOD; } modint operator/(modint &other){ return this->operator*(other.inv()); } modint operator/(modint &&other){ return this->operator*(other.inv()); } void operator/=(modint &other){ return this->operator*=(other.inv()); } void operator/=(modint &&other){ return this->operator*=(other.inv()); } modint pow(Int &x){ int b = 0; while(x >= (1ll << (b+1)))b++; modint ans = 1; for(;b >= 0;b--){ ans *= ans; if((x >> b) & 1)ans *= *this; } return ans; } modint pow(Int &&x){ int b = 0; while(x >= (1ll << (b+1)))b++; modint ans = 1; for(;b >= 0;b--){ ans *= ans; if((x >> b) & 1)ans *= *this; } return ans; } modint inv(){ return this->pow(MOD - 2); } }; using mint = modint<998244353>; void view(vector<mint> x){ for(auto e:x)cout << e.val<< " ";cout << endl; } vector<mint> operator+(vector<mint> &a, vector<mint> &b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] + b[i]; return ans; } vector<mint> operator+(vector<mint> &a, vector<mint> &&b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] + b[i]; return ans; } vector<mint> operator+(vector<mint> &&a, vector<mint> &b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] + b[i]; return ans; } vector<mint> operator+(vector<mint> &&a, vector<mint> &&b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] + b[i]; return ans; } vector<mint> operator-(vector<mint> &a, vector<mint> &b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] - b[i]; return ans; } vector<mint> operator-(vector<mint> &&a, vector<mint> &b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] - b[i]; return ans; } vector<mint> operator-(vector<mint> &a, vector<mint> &&b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] - b[i]; return ans; } vector<mint> operator-(vector<mint> &&a, vector<mint> &&b){ vector<mint> ans(max(a.size(), b.size()), 0); for(int i = 0;i < a.size();i++)ans[i] = ans[i] + a[i]; for(int i = 0;i < b.size();i++)ans[i] = ans[i] - b[i]; return ans; } vector<mint> operator*(mint k, vector<mint> a){ for(auto &elem:a)elem = elem * k; return a; } vector<mint> operator*(vector<mint> a, mint k){ for(auto &elem:a)elem = elem * k; return a; } vector<mint> operator/(vector<mint> a, mint k){ return a*(k.inv()); } vector<mint> fft(vector<mint> a){ int n = a.size(); mint w = mint(3).pow(998244352 / n); vector<mint> omegas(n); omegas[0] = 1; for(int i = 1;i < n;i++)omegas[i] = omegas[i-1] * w; int reversed_bit = 0; int b = 0; while((1 << b) != n)b++; b--; for(int i = 0;i < n;i++){ if(i < reversed_bit){ swap(a[i], a[reversed_bit]); } if(i == n-1)break; for(int j = b;j >= 0;j--){ reversed_bit ^= 1 << j; if(reversed_bit & (1 << j))break; } } for(int width = 1;width * 2 <= n;width *= 2){ for(int i = 0;i < n;i += width * 2){ for(int j = i;j < i + width;j++){ auto &sky = a[j]; auto &ground = a[j+width]; auto ground_w = ground * omegas[n/width/2 * (j-i)]; ground = sky - ground_w; sky = sky + ground_w; } } } return a; } vector<mint> invfft(vector<mint> &A){ reverse(A.begin() + 1, A.end()); auto ret = fft(A); reverse(A.begin() + 1, A.end()); return ret / A.size(); } vector<mint> convolution(vector<mint> &a, vector<mint> &b){ int n = 1; int as = a.size(), bs = b.size(); int ret_sz = a.size() + b.size() - 1; while(n < a.size() * 2 || n < b.size() * 2)n <<= 1; a.resize(n, 0); b.resize(n, 0); auto A = move(fft(a)); auto B = move(fft(b)); a.resize(as); b.resize(bs); for(int i = 0;i < n;i++)A[i] *= B[i]; auto c = invfft(A); c.resize(ret_sz); return c; } vector<mint> convolution(vector<mint> &a, vector<mint> &&b){ int n = 1; int as = a.size(), bs = b.size(); int ret_sz = a.size() + b.size() - 1; while(n < a.size() * 2 || n < b.size() * 2)n <<= 1; a.resize(n, 0); b.resize(n, 0); auto A = move(fft(a)); auto B = move(fft(b)); a.resize(as); b.resize(bs); for(int i = 0;i < n;i++)A[i] *= B[i]; auto c = invfft(A); c.resize(ret_sz); return c; } vector<mint> convolution(vector<mint> &&a, vector<mint> &b){ int n = 1; int as = a.size(), bs = b.size(); int ret_sz = a.size() + b.size() - 1; while(n < a.size() * 2 || n < b.size() * 2)n <<= 1; a.resize(n, 0); b.resize(n, 0); auto A = move(fft(a)); auto B = move(fft(b)); a.resize(as); b.resize(bs); for(int i = 0;i < n;i++)A[i] *= B[i]; auto c = invfft(A); c.resize(ret_sz); return c; } vector<mint> convolution(vector<mint> &&a, vector<mint> &&b){ int n = 1; int as = a.size(), bs = b.size(); int ret_sz = a.size() + b.size() - 1; while(n < a.size() * 2 || n < b.size() * 2)n <<= 1; a.resize(n, 0); b.resize(n, 0); auto A = move(fft(a)); auto B = move(fft(b)); a.resize(as); b.resize(bs); for(int i = 0;i < n;i++)A[i] *= B[i]; auto c = invfft(A); c.resize(ret_sz); return c; } vector<mint> inv_fps(vector<mint> &a){ int d = 1; vector<mint> x = {a[0].inv()}; vector<mint> tmpa = {a[0]}; while(d < a.size()){ d *= 2; x.resize(d, 0); tmpa.resize(d,0); for(int i = d/2;i < d && i < a.size();i++){ tmpa[i] = a[i]; } x = 2 * x - convolution(tmpa, convolution(x, x)); x.resize(d); } x.resize(a.size()); return x; } vector<mint> inv_fps(vector<mint> &&a){ int d = 1; vector<mint> x = {a[0].inv()}; vector<mint> tmpa = {a[0]}; while(d < a.size()){ d *= 2; x.resize(d, 0); tmpa.resize(d,0); for(int i = d/2;i < d && i < a.size();i++){ tmpa[i] = a[i]; } x = 2 * x - convolution(tmpa, convolution(x, x)); x.resize(d); } x.resize(a.size()); return x; } vector<mint> log_fps(vector<mint> a){ int n = a.size(); auto a_inv = inv_fps(a); for(int i = 0;i < a.size() - 1;i++){ a[i] = a[i+1] * (i+1); } a.back() = 0; a = move(convolution(a, a_inv)); a.resize(n); for(int i = a.size() - 1;i > 0;i--){ a[i] = a[i-1] * mint(i).inv(); } a[0] = 0; return a; } vector<mint> exp_fps(vector<mint> &a){ int d = 1; vector<mint> x = {1}; vector<mint> one = {1}; vector<mint> tmpa = {a[0] + 1}; while(d < a.size()){ d *= 2; x.resize(d, 0); tmpa.resize(d, 0); for(int i = d/2;i < d && i < a.size();i++){ tmpa[i] = a[i]; } x = convolution(x, tmpa - log_fps(x)); x.resize(d); } x.resize(a.size()); return x; } vector<mint> exp_fps(vector<mint> &&a){ int d = 1; vector<mint> x = {1}; vector<mint> one = {1}; vector<mint> tmpa = {a[0] + 1}; while(d < a.size()){ d *= 2; x.resize(d, 0); tmpa.resize(d, 0); for(int i = d/2;i < d && i < a.size();i++){ tmpa[i] = a[i]; } x = convolution(x, tmpa - log_fps(x)); x.resize(d); } x.resize(a.size()); return x; } vector<mint> pow_fps(vector<mint> a, int m){ int n = a.size(); Int first_nonzero = 0; while(first_nonzero < n && a[first_nonzero].val == 0)first_nonzero++; if(first_nonzero == n)return a; rotate(a.begin(), a.begin() + first_nonzero, a.end()); first_nonzero *= m; if(first_nonzero >= n)return vector<mint>(n, 0); a = a[0].pow(m) * exp_fps(m * log_fps(a[0].inv() * a)); rotate(a.begin(), a.end() - first_nonzero, a.end()); fill(a.begin(), a.begin() + first_nonzero, 0); return a; } Int mod_log(Int g, Int x, Int mod=MOD){ Int b = 1; while(b * b < mod)b++; map<Int, int> bs; Int xi = 1; for(int i = 0;i < b;i++){ bs[xi] = i; (xi *= g) %= mod; } Int xbi = 1; for(int i = 1;i <= b;i++){ (xbi *= xi) %= MOD; if(bs.count(xbi * x % mod)){ return (mod - 1 - i * b + bs[xbi*x%mod]) % (mod - 1); } } return -1; } vector<mint> sqrt_fps(vector<mint> a){ Int n = a.size(); Int first_nonzero = 0; while(first_nonzero < n && a[first_nonzero].val == 0)first_nonzero++; if(first_nonzero == n)return a; if(first_nonzero % 2 == 1)return {}; rotate(a.begin(), a.begin() + first_nonzero, a.end()); Int c = a[0].val; Int mod_log_c = mod_log(3, c); if(mod_log_c % 2 == 1)return {}; mint sqrt_c = mint(3).pow(mod_log_c / 2); int d = 1; mint inv_2 = mint(2).inv(); vector<mint> x = {sqrt_c}; vector<mint> tmpa = {a[0]}; while(d < a.size()){ d *= 2; x.resize(d, 0); tmpa.resize(d, 0); for(int i = d / 2;i < d && i < a.size();i++){ tmpa[i] = a[i]; } x = inv_2 * x + convolution(tmpa, inv_fps(2 * x)); x.resize(d); } x.resize(a.size()); rotate(x.begin(), x.end() - first_nonzero / 2,x.end()); for(int i = 0;i < first_nonzero / 2;i++)x[i] = 0; return x; } int main(){ int n; cin >> n; vector<mint> a(n); for(int i = 0;i < n;i++){ int x; cin >> x; a[i] = x; } auto ans = log_fps(a); // auto ans = convolution(a, a); if(ans.empty())cout << -1 << endl; else {for(auto elem:ans)cout << elem.val <<" ";cout << endl;} return 0; }