結果
問題 | No.2556 Increasing Matrix |
ユーザー | tko919 |
提出日時 | 2023-12-02 01:27:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 6,000 ms |
コード長 | 20,045 bytes |
コンパイル時間 | 3,438 ms |
コンパイル使用メモリ | 236,160 KB |
実行使用メモリ | 56,516 KB |
最終ジャッジ日時 | 2024-09-26 16:12:41 |
合計ジャッジ時間 | 9,712 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,632 KB |
testcase_01 | AC | 6 ms
5,632 KB |
testcase_02 | AC | 5 ms
5,760 KB |
testcase_03 | AC | 6 ms
5,632 KB |
testcase_04 | AC | 6 ms
5,632 KB |
testcase_05 | AC | 6 ms
5,632 KB |
testcase_06 | AC | 6 ms
5,632 KB |
testcase_07 | AC | 6 ms
5,632 KB |
testcase_08 | AC | 7 ms
5,504 KB |
testcase_09 | AC | 10 ms
6,016 KB |
testcase_10 | AC | 7 ms
5,760 KB |
testcase_11 | AC | 10 ms
5,888 KB |
testcase_12 | AC | 8 ms
5,760 KB |
testcase_13 | AC | 17 ms
6,400 KB |
testcase_14 | AC | 29 ms
7,168 KB |
testcase_15 | AC | 28 ms
7,040 KB |
testcase_16 | AC | 27 ms
7,040 KB |
testcase_17 | AC | 50 ms
8,448 KB |
testcase_18 | AC | 575 ms
31,600 KB |
testcase_19 | AC | 1,058 ms
54,108 KB |
testcase_20 | AC | 1,079 ms
54,680 KB |
testcase_21 | AC | 532 ms
30,744 KB |
testcase_22 | AC | 59 ms
8,576 KB |
testcase_23 | AC | 1,155 ms
56,516 KB |
testcase_24 | AC | 1,135 ms
56,516 KB |
ソースコード
#line 1 "library/Template/template.hpp" #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end()) #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v,x) lower_bound(ALL(v),(x))-(v).begin() #define UB(v,x) upper_bound(ALL(v),(x))-(v).begin() using ll=long long int; using ull=unsigned long long; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;} template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);} template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);} template<typename T>int popcnt(T x){return __builtin_popcountll(x);} template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));} template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));} #line 2 "library/Utility/fastio.hpp" #include <unistd.h> class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){ x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48)); } return true; } inline bool _read(__int128_t& x){ if(!skip())return false; if(rdLeft+40>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){ x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48)); } return true; } inline bool _read(__uint128_t& x){ if(!skip())return false; if(rdLeft+40>=rdRight)reload(); x=0; while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){ x=x*10+(rdbuf[rdLeft++]^48); } return true; } template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){ x=x*10+(rdbuf[rdLeft++]^48); } if(rdbuf[rdLeft]!='.')return true; rdLeft++; T base=.1; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){ x+=base*(rdbuf[rdLeft++]^48); base*=.1; } if(neg)x=-x; return true; } inline bool _read(char& x){ if(!skip())return false; if(rdLeft+1>=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos<rdRight and rdbuf[pos]>' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } template<typename T>inline bool _read(vector<T>& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__int128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__uint128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } template<typename T>inline void _write(const vector<T>& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');} template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){ if(space)_write(' '); _write(head); write<ln,true>(tail...); } }; /** * @brief Fast IO */ #line 3 "sol.cpp" #line 2 "library/Math/modint.hpp" template<int mod=1000000007>struct fp { int v; static constexpr int get_mod(){return mod;} int inv() const{ int tmp,a=v,b=mod,x=1,y=0; while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y); if(x<0){x+=mod;} return x; } fp(ll x=0){init(x%mod+mod);} fp& init(ll x){v=(x<mod?x:x-mod); return *this;} fp operator-()const{return fp()-*this;} fp pow(ll t){assert(t>=0); fp res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;} return res;} fp& operator+=(const fp& x){return init(v+x.v);} fp& operator-=(const fp& x){return init(v+mod-x.v);} fp& operator*=(const fp& x){v=ll(v)*x.v%mod; return *this;} fp& operator/=(const fp& x){v=ll(v)*x.inv()%mod; return *this;} fp operator+(const fp& x)const{return fp(*this)+=x;} fp operator-(const fp& x)const{return fp(*this)-=x;} fp operator*(const fp& x)const{return fp(*this)*=x;} fp operator/(const fp& x)const{return fp(*this)/=x;} bool operator==(const fp& x)const{return v==x.v;} bool operator!=(const fp& x)const{return v!=x.v;} friend istream& operator>>(istream& is,fp& x){return is>>x.v;} friend ostream& operator<<(ostream& os,const fp& x){return os<<x.v;} }; /** * @brief Modint */ #line 2 "library/Convolution/ntt.hpp" template<typename T,unsigned p=3>struct NTT{ vector<T> rt,irt; NTT(int lg=21){ unsigned m=T::get_mod()-1; T prt=p; rt.resize(lg); irt.resize(lg); rep(k,0,lg){ rt[k]=-prt.pow(m>>(k+2)); irt[k]=rt[k].inv(); } } void ntt(vector<T>& f,bool inv=0){ int n=f.size(); if(inv){ for(int m=1;m<n;m<<=1){ T w=1; for(int s=0,t=0;s<n;s+=m*2){ for(int i=s,j=s+m;i<s+m;i++,j++){ auto x=f[i],y=f[j]; f[i]=x+y; f[j]=(x-y)*w; } w*=irt[__builtin_ctz(++t)]; } } T mul=T(n).inv(); rep(i,0,n)f[i]*=mul; }else{ for(int m=n;m>>=1;){ T w=1; for(int s=0,t=0;s<n;s+=m*2){ for(int i=s,j=s+m;i<s+m;i++,j++){ auto x=f[i],y=f[j]*w; f[i]=x+y; f[j]=x-y; } w*=rt[__builtin_ctz(++t)]; } } } } vector<T> mult(const vector<T>& a,const vector<T>& b,bool same=0){ if(a.empty() or b.empty())return vector<T>(); int n=a.size()+b.size()-1,m=1<<__lg(n*2-1); vector<T> res(m); rep(i,0,a.size()){res[i]=a[i];} ntt(res); if(same)rep(i,0,m)res[i]*=res[i]; else{ vector<T> c(m); rep(i,0,b.size())c[i]=b[i]; ntt(c); rep(i,0,m)res[i]*=c[i]; } ntt(res,1); res.resize(n); return res; } }; /** * @brief Number Theoretic Transform */ #line 2 "library/FPS/fps.hpp" template<typename T>struct Poly:vector<T>{ Poly(int n=0){this->assign(n,T());} Poly(const initializer_list<T> f):vector<T>::vector(f){} Poly(const vector<T>& f){this->assign(ALL(f));} T eval(const T& x){ T res; for(int i=this->size()-1;i>=0;i--)res*=x,res+=this->at(i); return res; } Poly rev()const{Poly res=*this; reverse(ALL(res)); return res;} void shrink(){while(!this->empty() and this->back()==0)this->pop_back();} Poly operator>>(int sz)const{ if((int)this->size()<=sz)return {}; Poly ret(*this); ret.erase(ret.begin(),ret.begin()+sz); return ret; } Poly operator<<(int sz)const{ Poly ret(*this); ret.insert(ret.begin(),sz,T(0)); return ret; } vector<T> mult(const vector<T>& a,const vector<T>& b,bool same=0)const{ if(a.empty() or b.empty())return vector<T>(); int n=a.size()+b.size()-1,m=1<<__lg(n*2-1); vector<T> res(m); rep(i,0,a.size())res[i]=a[i]; NTT(res,0); if(same)rep(i,0,m)res[i]*=res[i]; else{ vector<T> c(m); rep(i,0,b.size())c[i]=b[i]; NTT(c,0); rep(i,0,m)res[i]*=c[i]; } NTT(res,1); res.resize(n); return res; } Poly square()const{return Poly(mult(*this,*this,1));} Poly operator-()const{return Poly()-*this;} Poly operator+(const Poly& g)const{return Poly(*this)+=g;} Poly operator+(const T& g)const{return Poly(*this)+=g;} Poly operator-(const Poly& g)const{return Poly(*this)-=g;} Poly operator-(const T& g)const{return Poly(*this)-=g;} Poly operator*(const Poly& g)const{return Poly(*this)*=g;} Poly operator*(const T& g)const{return Poly(*this)*=g;} Poly operator/(const Poly& g)const{return Poly(*this)/=g;} Poly operator/(const T& g)const{return Poly(*this)/=g;} Poly operator%(const Poly& g)const{return Poly(*this)%=g;} pair<Poly,Poly> divmod(const Poly& g)const{ Poly q=*this/g,r=*this-g*q; r.shrink(); return {q,r}; } Poly& operator+=(const Poly& g){ if(g.size()>this->size())this->resize(g.size()); rep(i,0,g.size()){(*this)[i]+=g[i];} return *this; } Poly& operator+=(const T& g){ if(this->empty())this->push_back(0); (*this)[0]+=g; return *this; } Poly& operator-=(const Poly& g){ if(g.size()>this->size())this->resize(g.size()); rep(i,0,g.size()){(*this)[i]-=g[i];} return *this; } Poly& operator-=(const T& g){ if(this->empty())this->push_back(0); (*this)[0]-=g; return *this; } Poly& operator*=(const Poly& g){ *this=mult(*this,g,0); return *this; } Poly& operator*=(const T& g){ rep(i,0,this->size())(*this)[i]*=g; return *this; } Poly& operator/=(const Poly& g){ if(g.size()>this->size()){ this->clear(); return *this; } Poly g2=g; reverse(ALL(*this)); reverse(ALL(g2)); int n=this->size()-g2.size()+1; this->resize(n); g2.resize(n); *this*=g2.inv(); this->resize(n); reverse(ALL(*this)); shrink(); return *this; } Poly& operator/=(const T& g){ rep(i,0,this->size())(*this)[i]/=g; return *this; } Poly& operator%=(const Poly& g){*this-=*this/g*g; shrink(); return *this;} Poly diff()const{ Poly res(this->size()-1); rep(i,0,res.size())res[i]=(*this)[i+1]*(i+1); return res; } Poly inte()const{ Poly res(this->size()+1); for(int i=res.size()-1;i;i--)res[i]=(*this)[i-1]/i; return res; } Poly log()const{ assert(this->front()==1); const int n=this->size(); Poly res=diff()*inv(); res=res.inte(); res.resize(n); return res; } Poly shift(const int& c)const{ const int n=this->size(); Poly res=*this,g(n); g[0]=1; rep(i,1,n)g[i]=g[i-1]*c/i; vector<T> fact(n,1); rep(i,0,n){ if(i)fact[i]=fact[i-1]*i; res[i]*=fact[i]; } res=res.rev(); res*=g; res.resize(n); res=res.rev(); rep(i,0,n)res[i]/=fact[i]; return res; } Poly inv()const{ const int n=this->size(); Poly res(1); res.front()=T(1)/this->front(); for(int k=1;k<n;k<<=1){ Poly f(k*2),g(k*2); rep(i,0,min(n,k*2))f[i]=(*this)[i]; rep(i,0,k)g[i]=res[i]; NTT(f,0); NTT(g,0); rep(i,0,k*2)f[i]*=g[i]; NTT(f,1); rep(i,0,k){f[i]=0; f[i+k]=-f[i+k];} NTT(f,0); rep(i,0,k*2)f[i]*=g[i]; NTT(f,1); rep(i,0,k)f[i]=res[i]; swap(res,f); } res.resize(n); return res; } Poly exp()const{ const int n=this->size(); if(n==1)return Poly({T(1)}); Poly b(2),c(1),z1,z2(2); b[0]=c[0]=z2[0]=z2[1]=1; b[1]=(*this)[1]; for(int k=2;k<n;k<<=1){ Poly y=b; y.resize(k*2); NTT(y,0); z1=z2; Poly z(k); rep(i,0,k)z[i]=y[i]*z1[i]; NTT(z,1); rep(i,0,k>>1)z[i]=0; NTT(z,0); rep(i,0,k)z[i]*=-z1[i]; NTT(z,1); c.insert(c.end(),z.begin()+(k>>1),z.end()); z2=c; z2.resize(k*2); NTT(z2,0); Poly x=*this; x.resize(k); x=x.diff();x.resize(k); NTT(x,0); rep(i,0,k)x[i]*=y[i]; NTT(x,1); Poly bb=b.diff(); rep(i,0,k-1)x[i]-=bb[i]; x.resize(k*2); rep(i,0,k-1){x[k+i]=x[i]; x[i]=0;} NTT(x,0); rep(i,0,k*2)x[i]*=z2[i]; NTT(x,1); x.pop_back(); x=x.inte(); rep(i,k,min(n,k*2))x[i]+=(*this)[i]; rep(i,0,k)x[i]=0; NTT(x,0); rep(i,0,k*2)x[i]*=y[i]; NTT(x,1); b.insert(b.end(),x.begin()+k,x.end()); } b.resize(n); return b; } Poly pow(ll t){ if(t==0){ Poly res(this->size()); res[0]=1; return res; } int n=this->size(),k=0; while(k<n and (*this)[k]==0)k++; Poly res(n); if(__int128_t(t)*k>=n)return res; n-=t*k; Poly g(n); T c=(*this)[k],ic=c.inv(); rep(i,0,n)g[i]=(*this)[i+k]*ic; g=g.log(); for(auto& x:g)x*=t; g=g.exp(); c=c.pow(t); rep(i,0,n)res[i+t*k]=g[i]*c; return res; } void NTT(vector<T>& a,bool inv)const; }; /** * @brief Formal Power Series (NTT-friendly mod) */ #line 7 "sol.cpp" using Fp=fp<998244353>; NTT<Fp,3> ntt; template<>void Poly<Fp>::NTT(vector<Fp>& v,bool inv)const{return ntt.ntt(v,inv);} #line 2 "library/FPS/multieval.hpp" template<typename T>struct MultiEval{ int m,n; vector<Poly<T>> t; MultiEval(vector<T>& v){ m=v.size(),n=1; while(n<m)n<<=1; t.resize(n<<1); rep(i,0,n){ T w=(i<m?v[i]:0); t[n+i]=Poly<T>({-w,T(1)}); } for(int i=n-1;i;i--)t[i]=t[i*2]*t[i*2+1]; } vector<T> run(const vector<T>& f){ if(f.empty())return vector<T>(m); vector<Poly<T>> c(n*2); auto v=t[1].rev(); v.resize(f.size()); v=v.inv().rev()*Poly<T>(f); v.erase(v.begin(),v.begin()+f.size()-1); v.resize(n); reverse(ALL(v)); c[1]=v; rep(i,1,n){ int d=c[i].size(); rep(k,0,2){ auto add=t[i*2+(k^1)]; add.resize(d/2+1); add=add.rev(); add*=c[i]; add.resize(d); c[i*2+k]=vector<T>(add.begin()+d/2,add.end()); } } vector<T> res(m); rep(i,0,m)res[i]=c[n+i][0]; return res; } vector<T> build(vector<T>& ys){ auto w=t[1].rev(); w.resize(m+1); auto vs=run(w.rev().diff()); rep(i,0,m)ys[i]/=vs[i]; vector<Poly<T>> c(n*2); rep(i,0,n){ if(i<m)c[n+i]=Poly<T>({ys[i]}); else c[n+i]=Poly<T>({T()}); } for(int i=n-1;i;i--)c[i]=c[i*2]*t[i*2+1]+c[i*2+1]*t[i*2]; c[1]=vector<T>(c[1].begin()+(n-m),c[1].end()); c[1].resize(m); return c[1]; } }; /** * @brief Multipoint Evaluation */ #line 2 "library/FPS/prodofpolys.hpp" template<typename T>Poly<T> ProdOfPolys(vector<Poly<T>>& fs){ if(fs.empty())return Poly<T>({T(1)}); sort(ALL(fs),[&](Poly<T>& a,Poly<T>& b){return a.size()<b.size();}); deque<Poly<T>> deq; for(auto& f:fs)deq.push_back(f); while(deq.size()>1){ deq.push_back(deq[0]*deq[1]); deq.pop_front(); deq.pop_front(); } return deq[0]; } /** * @brief Product of Polynomials */ #line 2 "library/Math/factorial.hpp" template<typename T>struct factorial { vector<T> Fact,Finv,Inv; factorial(int maxx){ Fact.resize(maxx); Finv.resize(maxx); Inv.resize(maxx); Fact[0]=Fact[1]=Finv[0]=Finv[1]=Inv[1]=1; rep(i,2,maxx){Fact[i]=Fact[i-1]*i;} Finv[maxx-1]=T(1)/Fact[maxx-1]; for(int i=maxx-1;i>=2;i--){Finv[i-1]=Finv[i]*i; Inv[i]=Finv[i]*Fact[i-1];} } T fact(int n,bool inv=0){if(n<0)return 0; return (inv?Finv[n]:Fact[n]);} T inv(int n){if(n<0)return 0; return Inv[n];} T nPr(int n,int r,bool inv=0){if(n<0||n<r||r<0)return 0; return fact(n,inv)*fact(n-r,inv^1);} T nCr(int n,int r,bool inv=0){if(n<0||n<r||r<0)return 0; return fact(n,inv)*fact(r,inv^1)*fact(n-r,inv^1);} T nHr(int n,int r,bool inv=0){return nCr(n+r-1,r,inv);} }; /** * @brief Factorial */ #line 14 "sol.cpp" factorial<Fp> fact(201010); FastIO io; int main(){ int n; io.read(n); vector<int> a(n); io.read(a); rep(i,0,n)a[i]+=i; Fp ret=1; // rep(i,0,n)rep(j,i+1,n)ret*=(a[j]-a[i]); vector<Fp> A(ALL(a)); MultiEval<Fp> buf(A); vector<Poly<Fp>> fs; rep(i,0,n)fs.push_back(Poly<Fp>({-a[i],1})); auto f=ProdOfPolys(fs); f=f.diff(); auto vs=buf.run(f); for(auto& v:vs)ret*=v; if((ll(n)*(n-1)/2)&1)ret=-ret; rep(x,1,n)ret*=fact.fact(x,1)*fact.fact(x,1); io.write(ret.v); return 0; }