結果

問題 No.3443 Sum of (Tree Distances)^K 1
コンテスト
ユーザー askr58
提出日時 2026-02-06 22:49:36
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 7,640 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,688 ms
コンパイル使用メモリ 363,980 KB
実行使用メモリ 68,564 KB
最終ジャッジ日時 2026-02-06 22:49:49
合計ジャッジ時間 12,337 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 1 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include <atcoder/modint>
#include <atcoder/convolution>
using mint=atcoder::modint998244353;
struct FPS{
    vector<mint> f;
    
    FPS(){}
    FPS(int n){f.resize(n);}
    FPS(const vector<mint>& v):f(v){}
    template <typename T>
    FPS(int n,T val){f.resize(n,val);}

    int size() const{ return (int)f.size();}
    mint& operator[](int i){return f[i];}
    const mint& operator[](int i) const{return f[i];}
    void resize(int n) {f.resize(n);}
	void pop_back() {f.pop_back();}


    template <typename T>
    FPS(const vector<T>& v){
        f.resize(v.size());
        for(int i=0;i<v.size();i++)f[i]=v[i];
    }

    //演算
    FPS operator+(const FPS& other) const{
        int n=max(size(),other.size());
        FPS res(n);
        for(int i=0;i<n;i++){
            res[i]=(i<size()? (*this)[i]:0) + (i<other.size()? other[i]:0);
        }
        return res;
    }
    FPS operator-(const FPS& other) const{
        int n=max(size(),other.size());
        FPS res(n);
        for(int i=0;i<n;i++){
            res[i]=(i<size()? (*this)[i]:0) + (i<other.size()? -other[i]:0);

        }
        return res;
    }
    
    FPS operator-()const{
        return FPS(size())-(*this);
    }
    
    FPS operator*(const FPS& other) const{
        return FPS(atcoder::convolution(this->f,other.f));
    }
    
    template <typename T>
    FPS operator*(const T& c) const{
        FPS res(*this);
        for(auto& x:res.f)x*=c;
        return res;
    }
    
    template <typename T>
    FPS operator/(const T& c) const{
        assert(c!=0);
        FPS res(*this);
        for(auto& x:res.f)x/=c;
        return res;
    }
        
    FPS& operator+=(const FPS& other) {return *this = *this + other;}
    FPS& operator-=(const FPS& other) {return *this = *this - other;}
    template <typename T>
    FPS& operator*=(const T& c){return *this = *this * c;}
    template <typename T>
    FPS& operator/=(const T& c){return *this = *this / c;}
   

    //もろもろ

    FPS diff(int sz=-1) const{
        if(size()==0)return (*this);
        if(sz==-1)sz=size();
        FPS res(sz-1);
        for(int i=1;i<min(sz+1,size());i++)res[i-1]=i*(*this)[i];
        return res;
    }

    FPS integ(int sz=-1) const{
        if(sz==-1)sz=size();
        FPS res(sz+1);
        for(int i=0;i<min(sz,size());i++)res[i+1]=(*this)[i]/(i+1);
        return res;
    }

    FPS inv(int sz=-1) const{
        assert((*this)[0]!=0);
        if(sz==-1)sz=size();
        FPS res(1);
        res.f[0]=(*this)[0].inv();
        while(res.size()<sz){
            int n=res.size();
            FPS tmp=-(*this)*res;
            tmp.resize(2*n);
            tmp[0]+=2;
            res*=tmp;
            res.resize(2*n);
        }
        res.resize(sz);
        return res;
    }
    
    FPS log(int sz=-1) const{
        assert((*this)[0]==1);
        if(sz==-1)sz=size();
        FPS res=((*this).diff(sz) * (*this).inv(sz)).integ(sz);
        res.resize(sz);
        return res;
    }

    FPS exp(int sz=-1) const{
        assert((*this)[0]==0);
        if(sz==-1)sz=size();
        FPS res(1);
        res[0]=1;
        while(res.size()<sz){
            int n=res.size();
            res+=res*((*this)-res.log(2*n));  
            res.resize(2*n);
        }
        res.resize(sz);
        return res;
    }

	FPS pow(ll n) const{
		FPS f=this->log();
		for(int i=0;i<f.size();i++)f[i]*=n;
		return f.exp();
	}

    friend ostream& operator<<(ostream& os,const FPS& f){
        for(int i=0;i<f.size();i++)os<<f[i].val()<<(i+1==f.size()?"":" ");
        return os;
    }

    
};

template <typename T>
FPS operator*(const T& c,const FPS& f){
    return f*c;
}

// f=g*q+rなる(q,r)
pair<FPS,FPS> div_mod(FPS f,FPS g){
	while(f.size()>0&&f[f.size()-1]==0)f.pop_back();
	while(g.size()>0&&g[g.size()-1]==0)g.pop_back();
	int n=f.size(),m=g.size();
	assert(m>0);
	if(n<m){
		f.resize(m);
		return make_pair(FPS(1,0),f);
	}
	FPS revf(f.size()),revg(g.size());
	for(int i=0;i<f.size();i++)revf[f.size()-i-1]=f[i];
	for(int i=0;i<g.size();i++)revg[g.size()-i-1]=g[i];
	FPS revq=revf*revg.inv(n-m+1);
	FPS q(n-m+1);
	for(int i=0;i<=n-m;i++)q[i]=revq[n-m-i];
	auto qg=q*g;
	FPS r(m);
	for(int i=0;i<m;i++){
		if(i<n)r[i]=f[i]-qg[i];
	}
	return make_pair(q,r);
}

template <typename T>
vector<mint> multipoint_evaluation(FPS f,vector<T> x){
	int n=f.size(),m=x.size();
	int sz=1;
	while(sz<m)sz*=2;
	x.resize(sz);
	vector<FPS> prods(sz*2);
	for(int i=0;i<sz;i++){
		prods[sz+i].resize(2);
		prods[sz+i][0]=-x[i];
		prods[sz+i][1]=1;
	}
	for(int i=sz-1;i>0;i--){
		prods[i]=prods[i*2]*prods[i*2+1];
	}
	vector<FPS> rems(sz*2);
	rems[1]=div_mod(f,prods[1]).second;
	for(int i=2;i<2*sz;i++){
		rems[i]=div_mod(rems[i/2],prods[i]).second;
	}
	vector<mint> res(m);
	for(int i=0;i<m;i++)res[i]=rems[i+sz][0];
	return res;
}
		
	
	
mint bostan_mori(FPS f,FPS g,ll n){
	while(n>0){
		FPS gn=g;
		for(int i=1;i<g.size();i+=2)gn[i]=-gn[i];
		f*=gn;g*=gn;
		vector<mint> fv,gv;
		for(int i=0;i<g.size();i+=2)gv.push_back(g[i]);
		if(n&1){
			for(int i=1;i<f.size();i+=2)fv.push_back(f[i]);
		}else{
			for(int i=0;i<f.size();i+=2)fv.push_back(f[i]);
		}
		n>>=1;
		f=FPS(fv);
		g=FPS(gv);
	}
	return f[0]/g[0];
}

// memo
// P/QのPを復元したいなら
// P=QS mod x^lでok
FPS berlekamp_massey(vector<mint> s){
	FPS C(1,1);
	FPS B(1,1);
	int m=1,l=0;
	mint b=1;
	int n=s.size();
	for(int i=0;i<n;i++){
		mint d=s[i];
		for(int j=1;j<=min(i,l);j++){
			d+=C[j]*s[i-j];
		}
		if(d.val()==0){
			m++;
			continue;
		}
		mint coef=d/b;
		FPS tmp=C;
		if(C.size()<B.size()+m){
			C.resize(B.size()+m);
		}
		for(int j=0;j<B.size();j++){
			C[j+m]-=coef*B[j];
		}
		if(2*l<=i){
			l=i+1-l;
			B=tmp;
			b=d;
			m=1;
		}else{
			m++;
		}
	}
	C.resize(l+1);
	return C;
}
// i=0,1,......,mについて、[x^k](g*f^i)を列挙する
vector<mint> power_projection(FPS f,FPS g,int m,int k){
	int szx=1,szy=2;
	while(szx<k+1)szx*=2;
	f.resize(4*szx);g.resize(4*szx);	
	mint f0=f[0];
	f[0]=0;
	for(int i=0;i<2*szx;i++){
		f[i+2*szx]=-f[i];
		f[i]=0;
		g[i+2*szx]=0;
	}
	f[0]=1;
	int n=2*szx*szy;
	while(k>0){
		FPS h=f;
		for(int i=0;i<szy;i++){
			for(int j=1;j<2*szx;j+=2)h[i*2*szx+j]=-h[i*2*szx+j];
		}
		auto fh=f*h,gh=g*h;
		FPS nf(n),ng(n);
		for(int i=0;i<szy*2;i++){
			for(int j=0;j<szx/2;j++){
				nf[i*szx+j]=fh[i*szx*2+2*j];
				ng[i*szx+j]=gh[i*szx*2+2*j+(k&1)];
			}
		}
		f=move(nf);g=move(ng);
		szy*=2;szx/=2;
		k/=2;
	}
	FPS P(szy),Q(szy);
	for(int i=0;i<szy;i++){
		P[i]=g[i*szx*2];
		Q[i]=f[i*szx*2];
	}
	FPS res0(m+1);
	FPS R=P*Q.inv(m+1);
	for(int i=0;i<=m;i++)res0[i]=R[i];
	vector<mint> fact(m+1,1),factinv(m+1,1);
	for(int i=0;i<m;i++){
		fact[i+1]=fact[i]*(i+1);
		factinv[i+1]=fact[i+1].inv();
	}
	for(int i=0;i<=m;i++)res0[i]*=factinv[i];
	FPS v(m+1);
	mint tmp=1;
	for(int i=0;i<=m;i++){
		v[i]=tmp*factinv[i];
		tmp*=f0;
	}
	res0*=v;
	vector<mint> res(m+1);
	for(int i=0;i<=m;i++)res[i]=res0[i]*fact[i];
	return res;
}
int main(){
	int n,k;
	cin>>n>>k;
	FPS T(n+1);
	vector<mint> fact(n+1,1),factinv(n+1,1);
	for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i;
	factinv[n]=fact[n].inv();
	for(int i=n-1;i>=0;i--)factinv[i]=factinv[i+1]*(i+1);
	T[1]=1;
	for(int i=2;i<=n;i++)T[i]=((mint)i).pow(i-2)*factinv[i]*i;
	T=T.exp();
	FPS S(n+2);
	for(int i=0;i<=n;i++)S[i+1]=T[i];
	FPS v(n+1);
	FPS e(1,1);
	auto U=power_projection(S,e,n,n);
	for(int i=1;i<=n;i++)v[i]=U[i]*fact[n-i]*((mint)i-1).pow(k);
	FPS u(n+1);
	for(int i=0;i<=n;i++)u[i]=factinv[i];
	FPS w=v*u;	
	mint sum=0;
	for(int a=1;a<=n;a++){
		mint ans=w[a]*fact[a]/2;
		ans-=sum;
		cout<<ans.val()<<endl;
		sum+=ans;
	}
}
0