結果

問題 No.2817 Competition
ユーザー nouka28nouka28
提出日時 2024-07-19 22:03:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 788 ms / 2,000 ms
コード長 7,727 bytes
コンパイル時間 5,856 ms
コンパイル使用メモリ 318,100 KB
実行使用メモリ 126,544 KB
最終ジャッジ日時 2024-07-19 22:03:54
合計ジャッジ時間 20,832 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 431 ms
120,704 KB
testcase_01 AC 418 ms
120,704 KB
testcase_02 AC 412 ms
120,832 KB
testcase_03 AC 782 ms
126,504 KB
testcase_04 AC 753 ms
126,540 KB
testcase_05 AC 746 ms
126,544 KB
testcase_06 AC 788 ms
126,412 KB
testcase_07 AC 754 ms
126,392 KB
testcase_08 AC 495 ms
121,344 KB
testcase_09 AC 490 ms
122,092 KB
testcase_10 AC 556 ms
122,884 KB
testcase_11 AC 596 ms
124,032 KB
testcase_12 AC 425 ms
120,832 KB
testcase_13 AC 516 ms
122,180 KB
testcase_14 AC 567 ms
123,212 KB
testcase_15 AC 517 ms
121,856 KB
testcase_16 AC 568 ms
123,208 KB
testcase_17 AC 544 ms
122,256 KB
testcase_18 AC 773 ms
126,416 KB
testcase_19 AC 453 ms
120,704 KB
testcase_20 AC 427 ms
120,704 KB
testcase_21 AC 410 ms
120,832 KB
testcase_22 AC 421 ms
120,704 KB
testcase_23 AC 421 ms
120,704 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
#define int long long

template<class mint>
struct FormalPowerSeries:vector<mint>{
	using vector<mint>::vector;
	using vector<mint>::operator=;
	using fps=FormalPowerSeries;
	using sfps=vector<pair<int,mint>>;

	fps& operator+=(const fps& g){
		if(g.size()>this->size())this->resize(g.size());
		for(int i=0;i<(int)g.size();i++)(*this)[i]+=g[i];
		return *this;
	}

	fps& operator+=(const mint& v){
		if(this->empty())this->resize(1);
		(*this)[0]+=v;
		return *this;
	}

	fps operator+(const fps& g)const{return fps(*this)+=g;}
	fps operator+(const mint& v)const{return fps(*this)+=v;}
	friend fps operator+(const mint& v,const fps& f){return f+v;}
	fps& operator+=(const int& v){*this+=mint(v);return *this;}
	fps operator+(const int& v){return fps(*this)+=v;;}
	friend fps operator+(const int& v,const fps& f){return f+v;}

	fps& operator-=(const fps& g){
		if(g.size()>this->size())this->resize(g.size());
		for(int i=0;i<(int)g.size();i++)(*this)[i]-=g[i];
		return *this;
	}

	fps& operator-=(const mint& v){
		if(this->empty())this->resize(1);
		(*this)[0]-=v;
		return *this;
	}
	fps operator-(const fps& g)const{return fps(*this)-=g;}
	fps operator-(const mint& v)const{return fps(*this)-=v;}
	friend fps operator-(const mint& v,const fps& f){return -(f-v);}
	fps& operator-=(const int& v){*this-=v;return *this;}
	fps operator-(const int& v){return fps(*this)-=v;}
	friend fps operator-(const int& v,const fps& f){return -(f-v);}

	fps operator-()const{return fps(*this)*=-1;}

	fps& operator*=(const mint& v){for(auto&e:*this)e*=v;return *this;}
	fps operator*(const mint& v)const{return fps(*this)*=v;}
	friend fps operator*(const mint& v,const fps& f){return f*v;}
	fps& operator*=(const int& v){*this*=mint(v);return *this;}
	fps operator*(const int& v)const{return fps(*this)*=v;}
	friend fps operator*(const int&v,const fps& f){return f*v;}

	fps& operator<<=(const int d){
		this->insert(this->begin(),d,0);
		return *this;
	}

	fps operator<<(const int d)const{return fps(*this)<<=d;}
	
	fps& operator>>=(const int d){
		this->erase(this->begin(),this->begin()+min((int)this->size(),d));
		return *this;
	}

	fps operator>>(const int d)const{return fps(*this)>>=d;}

	//fast
	fps& operator*=(const fps& g){
		*this=atcoder::convolution(*this,g);
		return *this;
	}
	
	//naive
	// fps& operator*=(const fps& g){
	// 	this->resize(this->size()+g.size()-1);
	// 	for(int i=(int)this->size()-1;i>=0;i--){
	// 		for(int j=1;j<=(int)g.size();j++){
	// 			if(i+j>=(int)this->size())break;
	// 			(*this)[i+j]+=(*this)[i]*g[j];
	// 		}
	// 		(*this)[i]*=g[0];
	// 	}
	// 	return *this;
	// }

	fps operator*(const fps& g)const{return fps(*this)*=g;}

	fps inv(int d)const{
		fps g={(*this)[0].inv()};
		for(int k=1;k<d;k*=2){
			g=(2-*this*g)*g;
			g.resize(2*k);
		}
		g.resize(d+1);
		return g;
	}

	fps& operator/=(const fps& g){return *this=fps(*this*=g.inv(this->size())).pre(this->size());}
	fps& operator/=(const mint& v){for(auto&e:*this)e/=v;return *this;}
	fps operator/(const fps& g)const{return fps(*this)/=g;}
	fps operator/(const mint& v)const{return fps(*this)/=v;}
	
	fps quotient(const fps& g)const{
		if(this->size()<g.size())return fps();
		return (fps(this->rev()/g.rev()).pre(this->size()-g.size()+1)).rev();
	}
	fps reminder(const fps& g)const{return fps(*this-this->quotient(g)*g).pre(g.size()-1);}
	
	pair<fps,fps> quotient_reminder(const fps& g)const{
		pair<fps,fps> res;
		res.first=this->quotient(g);
		res.second=fps(*this-res.first*g).pre(g.size()-1);
		return res;
	}
	
	void shrink(){
		while(this->size()&&this->back()==mint(0))this->pop_back();
	}
	fps rev()const{fps g(*this);reverse(g.begin(),g.end());return g;}
	fps dot(fps g)const{
		fps res(min(this->size(),g.size()));
		for(int i=0;i<(int)res.size();i++)res[i]=(*this)[i]*g[i];
		return res;
	}
	fps pre(int d)const{
		fps res(begin(*this),begin(*this)+min((int)this->size(),d));
		if((int)res.size()<d)res.resize(d);
		return res;
	}

	fps& operator*=(const sfps& g){
		auto it0=g.begin();
		mint g0=0;
		if(it0->first==0){
			g0=it0->second;
			it0++;
		}
		for(int i=this->size()-1;i>=0;i--){
			for(auto it=it0;it!=g.end();it++){
				auto[j,gj]=*it;
				if(i+j>=this->size())break;
				(*this)[i+j]+=(*this)[i]*gj;
			}
			(*this)[i]*=g0;
		}
		return *this;
	}
	fps operator*(const sfps& g)const{return fps(*this)*=g;}

	fps& operator/=(const sfps& g){
		auto it0=g.begin();
		assert(it0->first==0&&it0->second!=0);
		mint g0_inv=it0->second.inv();
		it0++;
		for(int i=0;i<(int)this->size();i++){
			(*this)[i]*=g0_inv;
			for(auto it=it0;it!=g.begin();it++){
				auto[j,gj]=*it;
				if(i+j>=this->size())break;
				(*this)[i+j]-=(*this)[i]*gj;
			}
		}
		return *this;
	}
	fps operator/(const sfps& g)const{return fps(*this)/=g;}

	fps pow(long long d,const fps& g)const{
		fps res={1},pow2=*this;
		while(d>0){
			if(d&1)res=(res*pow2).reminder(g);
			pow2=(pow2*pow2).reminder(g);
			d>>=1;
		}
		return res;
	}

	fps derivative()const{
		fps res;
		for(int i=1;i<(int)this->size();i++)res.push_back((*this)[i]*i);
		return res;
	}

	fps integral()const{
		fps res={0};
		for(int i=0;i<(int)this->size();i++)res.push_back((*this)[i]/(i+1));
		return res;
	}

	fps log(int d)const{
		return fps(this->derivative()*this->inv(d)).integral().pre(d);
	}

	fps exp(int d)const{
		fps g={1};
		for(int k=1;k<d;k*=2){
			g=g*(*this+1-g.log(2*k));
			g.resize(2*k);
		}
		return g.pre(d);
	}

	fps pow(long long k,int d)const{
		if(k==0){
			fps res(d,mint(0));
			if(d)res[0]=1;
			return res;
		}
		int i0=0;
		while(i0<(int)this->size()&&(*this)[i0]==mint(0))i0++;
		if(i0==(int)this->size())return fps(d,mint(0));
		mint c0=(*this)[i0];
		fps fs=(*this>>i0)/c0;
		if(i0>=(d+k-1)/k)return fps(d,mint(0));
		int ds=(int)(d-k*i0);
		fps gs=fps(mint(k)*fs.log(ds)).exp(ds);
		fps g=fps(gs*c0.pow(k))<<(int)(k*i0);
		return g;
	}

	friend istream& operator>>(istream& is,fps&f){
		for(auto&e:f)cin>>e;
		return is;
	}
	friend ostream& operator<<(ostream& os,const fps& f){
		if((int)f.size()==0)os<<0;
		else{
			for(int i=0;i<(int)f.size();i++){
				os<<f[i].val();
				if(i<(int)f.size()-1)os<<" ";
			}
			return os;
		}
		return os;
	}
};
using fps=FormalPowerSeries<mint>;
using sfps=vector<pair<int,mint>>;

template<long long mod,long long MAX_N>
struct factional_prime{
	long long inv_[MAX_N+1];
    long long fac_[MAX_N+1];
    long long fac_inv_[MAX_N+1];

    factional_prime(){
        inv_[0]=0;inv_[1]=fac_[0]=fac_[1]=fac_inv_[0]=fac_inv_[1]=1;
        for(long long i=2;i<=MAX_N;i++){
            inv_[i]=((mod-mod/i)*inv_[mod%i])%mod;
            fac_[i]=(fac_[i-1]*i)%mod;
            fac_inv_[i]=(fac_inv_[i-1]*inv_[i])%mod;
        }
    }
    long long inv(long long n){
        if(n<0)return 0;
        return inv_[n];
    }
    long long fac(long long n){
        if(n<0)return 0;
        return fac_[n];
    }
    long long finv(long long n){
        if(n<0)return 0;
        return fac_inv_[n];
    }
    long long nCr(long long n,long long r){
        if(n<r||n<0||r<0)return 0;
        return ((fac_[n]*fac_inv_[n-r])%mod*fac_inv_[r])%mod;
    }
    long long nPr(long long n,long long r){
        if(n<r||n<0||r<0)return 0;
        return (fac_[n]*fac_inv_[n-r])%mod;
    }
};

factional_prime<998244353,5000000> fp;

signed main(){
	int n;cin>>n;
	vector<int> a(n);for(auto&&e:a)cin>>e;
	
	auto prod=[&](auto prod,int l,int r)->fps {
		if(r-l==1){
			return fps({1,a[l]});
		}else{
			int m=(l+r)/2;
			return prod(prod,l,m)*prod(prod,m,r);
		}
	};

	fps f=prod(prod,0,n);
	mint ans=0;
	for(int i=0;i<=n;i++){
		ans+=f[i]*mint(i).pow(n-i);
	}
	cout<<ans.val()<<endl;
}
0