Submit Info #39740

Problem Lang User Status Time Memory
Log of Formal Power Series cpp unos AC 5447 ms 210.23 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.38 MiB
max_all_zero_00 AC 4835 ms 210.14 MiB
max_random_00 AC 5403 ms 210.23 MiB
max_random_01 AC 5367 ms 210.15 MiB
max_random_02 AC 5355 ms 210.14 MiB
max_random_03 AC 5368 ms 210.16 MiB
max_random_04 AC 5447 ms 210.21 MiB
near_262144_00 AC 2602 ms 101.02 MiB
near_262144_01 AC 2600 ms 100.98 MiB
near_262144_02 AC 5280 ms 204.77 MiB
random_00 AC 5306 ms 207.63 MiB
random_01 AC 5372 ms 209.40 MiB
random_02 AC 591 ms 27.50 MiB
random_03 AC 5330 ms 208.59 MiB
random_04 AC 5231 ms 205.02 MiB
small_degree_00 AC 1 ms 0.67 MiB
small_degree_01 AC 1 ms 0.65 MiB
small_degree_02 AC 1 ms 0.67 MiB
small_degree_03 AC 1 ms 0.67 MiB
small_degree_04 AC 1 ms 0.66 MiB
small_degree_05 AC 1 ms 0.68 MiB
small_degree_06 AC 1 ms 0.67 MiB
small_degree_07 AC 2 ms 0.68 MiB
small_degree_08 AC 1 ms 0.62 MiB
small_degree_09 AC 1 ms 0.66 MiB

#include<iostream> #include<algorithm> #include<vector> using namespace std; using Int = long long int; const Int MOD = 998244353; struct modint998244353{ Int val; modint998244353(Int v = 0){ if(0<= v && v < MOD) val = v; else{ val = v % MOD; if(val < 0) val += MOD; } } modint998244353 operator*(modint998244353 other){ return modint998244353(val*other.val); } modint998244353 operator+(modint998244353 other){ auto tmp = val + other.val; if(tmp > MOD) tmp -= MOD; return modint998244353(tmp); } modint998244353 operator-(modint998244353 other){ auto tmp = val - other.val; if(tmp < 0) tmp += MOD; return modint998244353(tmp); } modint998244353 pow(Int x){ if(x == 0)return 1; auto half = pow(x / 2); half = half * half; if(x % 2 == 1)half = half * *this; return half; } modint998244353 inv(){ return this->pow(MOD-2); } }; using modint = modint998244353; vector<modint> fft(vector<modint> a, int n, modint w = 0){ if(w.val == 0){ w = modint(3).pow(998244353 / n); } if(n == 1)return a; vector<modint> even(n / 2), odd(n / 2); for(int i = 0;i < n/2;i++){ even[i] = a[i*2]; odd[i] = a[i*2+1]; } auto E = fft(even, n / 2, w*w); auto O = fft(odd, n / 2 ,w*w); vector<modint> A(n, 0); auto wi = modint(1); for(int i = 0;i < n;i++){ A[i] = E[i % (n / 2)] + wi * O[i % (n / 2)]; wi = wi * w; } return A; } vector<modint> invfft(vector<modint> A, int n){ reverse(A.begin() + 1, A.end()); auto ret = fft(A, n); auto invn = modint(n).pow(998244353-2); for(auto &elem:ret)elem = elem * invn; return ret; } vector<modint> convolution(vector<modint> a, vector<modint> b){ int n = 1; int ret_sz = a.size() + b.size() - 1; while(n < a.size() * 2 || n < b.size() * 2) n <<= 1; a.resize(n, modint(0)); b.resize(n, modint(0)); auto A = fft(a, n); auto B = fft(b, n); for(int i = 0;i < n;i++)A[i] = A[i] * B[i]; auto c = invfft(A, n); c.resize(ret_sz); return c; } vector<modint> operator+(vector<modint> a, vector<modint> b){ vector<modint> 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<modint> operator-(vector<modint> a, vector<modint> b){ vector<modint> 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<modint> operator*(modint k, vector<modint> a){ for(auto &elem:a)elem = elem * k; return a; } vector<modint> inv_fps(vector<modint> a){ int d = 1; vector<modint> x = {a[0].inv()}; vector<modint> tmpa; while(d < a.size()){ d *= 2; x.resize(d, 0); while(tmpa.size() < d)tmpa.push_back(a[tmpa.size()]); x = 2 * x - convolution(tmpa, convolution(x, x)); x.resize(d); } x.resize(a.size()); return x; } vector<modint> log_fps(vector<modint> 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 = convolution(a_inv, a); a.resize(n); for(int i = a.size() - 1;i > 0;i--){ a[i] = a[i-1] * modint(i).inv(); } a[0] = 0; return a; } int main(){ int n; cin >> n; vector<modint> a(n, modint(0)); for(int i = 0;i < n;i++){ int x; cin >> x; a[i] = x; } auto ans = log_fps(a); for(auto elem:ans) cout << elem.val <<" "; cout << endl; }