結果
問題 | No.2513 Power Eraser |
ユーザー |
|
提出日時 | 2023-10-20 23:03:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,670 ms / 6,000 ms |
コード長 | 14,566 bytes |
コンパイル時間 | 4,050 ms |
コンパイル使用メモリ | 269,336 KB |
最終ジャッジ日時 | 2025-02-17 10:43:03 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
//https://yukicoder.me/submissions/650286#include <bits/stdc++.h>#include <unistd.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = long long;#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))#define ALL(x) begin(x), end(x)#define all(s) (s).begin(),(s).end()#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define se second//#define P pair<ll,ll>#define REP(i, n) for (int i = 0; i < (n); ++i)#define in scanner.read_int()const ll mod = 998244353;//const ll mod = 1000000007;const ll inf = 2000000000000000000ll;static const long double pi = 3.141592653589793;template<class T>void vcin(vector<ll> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}void YesNo(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}void YESNO(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;}template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;}template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else returnvector(arg,make_vector<T>(x,args...));}ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }void gbjsmzmfuuvdf(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(20);}class Scanner {vector<char> buffer;ssize_t n_written;ssize_t n_read;public:Scanner(): buffer(1024*1024) { do_read(); }int64_t read_int() {int64_t ret = 0, sgn = 1;int ch = current_char();while (isspace(ch)) { ch = next_char(); }if (ch == '-') { sgn = -1; ch = next_char(); }for (; isdigit(ch); ch = next_char())ret = (ret * 10) + (ch - '0');return sgn * ret;}private:void do_read() {ssize_t r = read(0, &buffer[0], buffer.size());if (r < 0) {throw runtime_error(strerror(errno));}n_written = r;n_read = 0;}inline int next_char() {++n_read;if (n_read == n_written) { do_read(); }return current_char();}inline int current_char() {return (n_read == n_written) ? EOF : buffer[n_read];}};enum Mode {FAST = 1,NAIVE = -1,};template <class T, Mode mode = FAST>struct FormalPowerSeries : std::vector<T> {using std::vector<T>::vector;using std::vector<T>::size;using std::vector<T>::resize;using F = FormalPowerSeries;F &operator+=(const F &g){for(int i=0;i<int(min((*this).size(),g.size()));i++){(*this)[i]+=g[i];}return *this;}F &operator+=(const T &t){assert(int((*this).size()));(*this)[0]+=t;return *this;}F &operator-=(const F &g) {for(int i=0;i<int(min((*this).size(),g.size()));i++){(*this)[i]-=g[i];}return *this;}F &operator-=(const T &t){assert(int((*this).size()));(*this)[0]-=t;return *this;}F &operator*=(const T &g) {for(int i=0;i<int((*this).size());i++){(*this)[i]*=g;}return *this;}F &operator/=(const T &g) {T div=g.inv();for(int i=0;i<int((*this).size());i++){(*this)[i]*=div;}return *this;}F &operator<<=(const int d) {int n=(*this).size();(*this).insert((*this).begin(),d,0);(*this).resize(n);return *this;}F &operator>>=(const int d) {int n=(*this).size();(*this).erase((*this).begin(),(*this).begin()+min(n, d));(*this).resize(n);return *this;}F &operator=(const std::vector<T> &v) {int n = (*this).size();for(int i = 0; i < n; ++i) (*this)[i] = v[i];return *this;}F operator-() const {F ret = *this;return ret * -1;}F &operator*=(const F &g) {if(mode==FAST) {int n=(*this).size();auto tmp=atcoder::convolution(*this,g);int f=tmp.size();(*this).resize(f);*this=tmp;return *this;}else{int n = (*this).size(), m = g.size();for(int i = n - 1; i >= 0; --i) {(*this)[i] *= g[0];for(int j = 1; j < std::min(i + 1, m); j++)(*this)[i] += (*this)[i - j] * g[j];}return *this;}}F &operator/=(const F &g) {if(mode == FAST){int n = (*this).size();(*this) = atcoder::convolution(*this, g.inv());return *this;}else{assert(g[0] != T(0));T ig0 = g[0].inv();int n = (*this).size(), m = g.size();for(int i = 0; i < n; ++i) {for(int j = 1; j < std::min(i + 1, m); ++j)(*this)[i] -= (*this)[i - j] * g[j];(*this)[i] *= ig0;}return *this;}}F &operator%=(const F &g) { return *this-=*this/g*g; }F operator*(const T &g) const { return F(*this)*=g;}F operator-(const T &g) const { return F(*this)-=g;}F operator*(const F &g) const { return F(*this)*=g;}F operator-(const F &g) const { return F(*this)-=g;}F operator+(const F &g) const { return F(*this)+=g;}F operator/(const F &g) const { return F(*this)/=g;}F operator%(const F &g) const { return F(*this)%=g;}F operator<<(const int d) const { return F(*this)<<=d;}F operator>>(const int d) const { return F(*this)>>=d;}void onemul(const int d,const T c){int n=(*this).size();for(int i=n-d-1;i>=0;i--){(*this)[i+d]+=(*this)[i]*c;}}void onediv(const int d,const T c){int n=(*this).size();for(int i=0;i<n-d;i++){(*this)[i+d]-=(*this)[i]*c;}}T eval(const T &t) const {int n = (*this).size();T res = 0, tmp = 1;for(int i = 0; i < n; ++i){res += (*this)[i] * tmp, tmp *= t;}return res;}F inv(int deg = -1) const {int n = (*this).size();assert(mode == FAST and n and (*this)[0] != 0);if(deg == -1) deg = n;assert(deg > 0);F res{(*this)[0].inv()};while(int(res.size()) < deg) {int m = res.size();F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);f.resize(m * 2), atcoder::internal::butterfly(f);r.resize(m * 2), atcoder::internal::butterfly(r);for(int i = 0; i < m * 2; ++i) f[i] *= r[i];atcoder::internal::butterfly_inv(f);f.erase(f.begin(), f.begin() + m);f.resize(m * 2), atcoder::internal::butterfly(f);for(int i = 0; i < m * 2; ++i) f[i] *= r[i];atcoder::internal::butterfly_inv(f);T iz = T(m * 2).inv();iz *= -iz;for(int i = 0; i < m; ++i) f[i] *= iz;res.insert(res.end(), f.begin(), f.begin() + m);}res.resize(deg);return res;}F &diff_inplace() {int n = (*this).size();for(int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;(*this)[n - 1] = 0;return *this;}F diff() const { F(*this).diff_inplace();}F &integral_inplace() {int n = (*this).size(), mod = T::mod();std::vector<T> inv(n);{inv[1] = 1;for(int i = 2; i < n; ++i)inv[i] = T(mod) - inv[mod % i] * (mod / i);}for(int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1];(*this)[0] = 0;return *this;}F integral() const { return F(*this).integral_inplace(); }F &log_inplace() {int n = (*this).size();assert(n and (*this)[0] == 1);F f_inv = (*this).inv();(*this).diff_inplace();(*this) *= f_inv;(*this).resize(n);(*this).integral_inplace();return *this;}F log() const { return F(*this).log_inplace(); }F &deriv_inplace() {int n = (*this).size();assert(n);for(int i = 2; i < n; ++i) (*this)[i] *= i;(*this).erase((*this).begin());(*this).push_back(0);return *this;}F deriv() const { return F(*this).deriv_inplace(); }F &exp_inplace() {int n = (*this).size();assert(n and (*this)[0] == 0);F g{1};(*this)[0] = 1;F h_drv((*this).deriv());for(int m = 1; m < n; m *= 2) {F f((*this).begin(), (*this).begin() + m);f.resize(2 * m), atcoder::internal::butterfly(f);auto mult_f = [&](F &p) {p.resize(2 * m);atcoder::internal::butterfly(p);for(int i = 0; i < 2 * m; ++i) p[i] *= f[i];atcoder::internal::butterfly_inv(p);p /= 2 * m;};if(m > 1) {F g_(g);g_.resize(2 * m), atcoder::internal::butterfly(g_);for(int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i];atcoder::internal::butterfly_inv(g_);T iz = T(-2 * m).inv();g_ *= iz;g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);}F t((*this).begin(), (*this).begin() + m);t.deriv_inplace();{F r{h_drv.begin(), h_drv.begin() + m - 1};mult_f(r);for(int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i];}t.insert(t.begin(), t.back());t.pop_back();t *= g;F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));v.resize(m);t.insert(t.begin(), m - 1, 0);t.push_back(0);t.integral_inplace();for(int i = 0; i < m; ++i) v[i] -= t[m + i];mult_f(v);for(int i = 0; i < std::min(n - m, m); ++i)(*this)[m + i] = v[i];}return *this;}F exp() const { return F(*this).exp_inplace(); }F &pow_inplace(long long k) {int n = (*this).size(), l = 0;assert(k >= 0);if(!k){for(int i = 0; i < n; ++i) (*this)[i] = !i;return *this;}while(l < n and (*this)[l] == 0) ++l;if(l > (n - 1) / k or l == n) return *this = F(n);T c = (*this)[l];(*this).erase((*this).begin(), (*this).begin() + l);(*this) /= c;(*this).log_inplace();(*this).resize(n - l * k);(*this) *= k;(*this).exp_inplace();(*this) *= c.pow(k);(*this).insert((*this).begin(), l * k, 0);return *this;}F pow(const long long k) const { return F(*this).pow_inplace(); }void spacemul(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();if (d == 0) g.erase(g.begin());else c = 0;for(int i=n-1;i>=0;i--){(*this)[i] *= c;for (auto &[j, b] : g) {if (j > i) break;(*this)[i] += (*this)[i-j] * b;}}}void spacediv(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();assert(d == 0 && c != T(0));T ic = c.inv();g.erase(g.begin());for(int i=0;i<n;i++){for (auto &[j, b] : g) {if (j > i) break;(*this)[i] -= (*this)[i-j] * b;}(*this)[i] *= ic;}}};using fps = FormalPowerSeries<atcoder::modint998244353, FAST>;using mint = modint998244353;constexpr ll MAX = 300000;ll fac[MAX],finv[MAX],inv[MAX];void COMinit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%mod;inv[i]=mod-inv[mod%i]*(mod/i)%mod;finv[i]=finv[i-1]*inv[i]%mod;}}ll COM(ll n,ll k){if(n<k) return 0;if(n<0||k<0) return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod;}ll HOM(ll n,ll k){if(n+k-1>=n-1&&n-1>=0){return COM(n+k-1,n-1);}else{return 0;}}template <class T> vector<T> operator-(vector<T> a) {for (auto&& e : a) e = -e;return a;}template <class T> vector<T>& operator+=(vector<T>& l, const vector<T>& r) {l.resize(max(l.size(), r.size()));for (int i = 0; i < (int)r.size(); ++i) l[i] += r[i];return l;}template <class T> vector<T> operator+(vector<T> l, const vector<T>& r) {return l += r;}template <class T> vector<T>& operator-=(vector<T>& l, const vector<T>& r) {l.resize(max(l.size(), r.size()));for (int i = 0; i < (int)r.size(); ++i) l[i] -= r[i];return l;}template <class T> vector<T> operator-(vector<T> l, const vector<T>& r) {return l -= r;}template <class T> vector<T> operator*(const vector<T>& l, const vector<T>& r) {return convolution(l,r);}template <class T> vector<T>& operator*=(vector<T>& l, const vector<T>& r) {return l = l * r;}template <class T> vector<T> inverse(const vector<T>& a) {assert(not a.empty() and not (a[0] == 0));vector<T> b{1 / a[0]};while (b.size() < a.size()) {vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size()));x *= b * b;b.resize(2 * b.size());for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = -x[i];}return {begin(b), begin(b) + a.size()};}template <class T> vector<T> operator/(vector<T> l, vector<T> r) {if (l.size() < r.size()) return {};reverse(begin(l), end(l)), reverse(begin(r), end(r));int n = l.size() - r.size() + 1;l.resize(n), r.resize(n);l *= inverse(r);return {rend(l) - n, rend(l)};}template <class T> vector<T>& operator/=(vector<T>& l, const vector<T>& r) {return l = l / r;}template <class T> vector<T> operator%(vector<T> l, const vector<T>& r) {if (l.size() < r.size()) return l;l -= l / r * r;return {begin(l), begin(l) + (r.size() - 1)};}template <class T> vector<T>& operator%=(vector<T>& l, const vector<T>& r) {return l = l % r;}template <class T>vector<T> multipoint_evaluation(const vector<T>& poly, const vector<T>& x) {int n = x.size();vector<vector<T>> t(2 * n);for (int i = 0; i < n; ++i) t[n + i] = {-x[i], 1};for (int i = n; i-- > 1; ) t[i] = t[2 * i] * t[2 * i + 1];t[1] = poly % t[1];for (int i = 2; i < 2 * n; ++i) t[i] = t[i / 2] % t[i];vector<T> res(n);for (int i = 0; i < n; ++i) res[i] = t[n + i][0];return res;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin>>N;vector<int> A(N);rep(i,N) cin>>A[i];auto calc = [&](auto self,int l,int r)->pair<mint,vector<mint>> {if (r==l+1){return {1,{-A[l],1}};}mint res_val = 1;vector<mint> res_poly = {1};int mid = (l+r)>>1;auto [l_val,l_p] = self(self,l,mid);auto [r_val,r_p] = self(self,mid,r);res_val = l_val * r_val;res_poly = l_p * r_p;vector<mint> left_a = {A.begin()+l,A.begin()+mid};vector<mint> right_a = {A.begin()+mid,A.begin()+r};rep(_,1){auto Y = multipoint_evaluation(l_p,right_a);for (auto y:Y){res_val *= y;}}return {res_val,res_poly};};auto [res_val,res_poly] = calc(calc,0,N);if (((ll)N*(N-1)/2ll) & 1){res_val = -res_val;}cout << res_val.val() << endl;}