結果

問題 No.1985 [Cherry 4th Tune] Early Summer Rain
ユーザー 👑 potato167potato167
提出日時 2022-05-27 02:32:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 9,957 bytes
コンパイル時間 3,782 ms
コンパイル使用メモリ 253,184 KB
実行使用メモリ 20,012 KB
最終ジャッジ日時 2024-10-09 06:41:18
合計ジャッジ時間 28,831 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 145 ms
7,376 KB
testcase_16 AC 354 ms
11,416 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 657 ms
18,436 KB
testcase_20 AC 279 ms
17,432 KB
testcase_21 AC 644 ms
18,300 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 959 ms
18,472 KB
testcase_25 AC 958 ms
18,472 KB
testcase_26 AC 949 ms
18,596 KB
testcase_27 AC 952 ms
18,472 KB
testcase_28 WA -
testcase_29 AC 946 ms
18,472 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 952 ms
18,472 KB
testcase_34 AC 958 ms
18,468 KB
testcase_35 WA -
testcase_36 AC 955 ms
18,476 KB
testcase_37 AC 943 ms
18,432 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 555 ms
16,668 KB
testcase_42 WA -
testcase_43 AC 916 ms
18,476 KB
testcase_44 WA -
testcase_45 AC 954 ms
18,468 KB
testcase_46 WA -
testcase_47 AC 558 ms
16,660 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using std::cout;
using std::cin;
using std::endl;
using ll=long long;
using ld=long double;
ll ILL=2167167167167167167;
const int INF=2100000000;
const ll mod=998244353;
#define rep(i,a) for (ll i=0;i<a;i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
void yneos(bool a){if(a) cout<<"Yes\n"; else cout<<"No\n";}
template<class T> void vec_out(vector<T> &p){for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}

#include <atcoder/convolution>
using namespace atcoder;



//参考 https://nyaannyaan.github.io/library/fps/formal-power-series.hpp.html
namespace po167{

long long rev(long long a,long long MOD){
    long long D=1,C=MOD-2;
    while(C){
        if(C&1) D=(D*a)%MOD;
        C>>=1;
        a=(a*a)%MOD;
    }
    return D;
}
template <unsigned int mod = 998244353>
std::vector<long long> add_Polynomial(std::vector<long long> &p,std::vector<long long> &q){
	std::vector<long long> r(std::max(p.size(),q.size()));
	for(int i=0;i<(int)r.size();i++){
		if((int)p.size()>i) r[i]=p[i];
		if((int)q.size()>i) r[i]=(r[i]+q[i])%mod;
	}
	return r;
}
template <unsigned int mod = 998244353>
std::vector<long long> sub_Polynomial(std::vector<long long> &p,std::vector<long long> &q){
	std::vector<long long> r(std::max(p.size(),q.size()));
	for(int i=0;i<(int)r.size();i++){
		if((int)p.size()>i) r[i]=p[i];
		if((int)q.size()>i) r[i]=(r[i]-q[i]);
        if(r[i]<0) r[i]=(r[i]%mod+mod)%mod;
	}
	return r;
}
template <unsigned int mod = 998244353>
long long substitution_Polynomial(std::vector<long long> &p,long long x){
	long long ans=0;
	long long D=1;
	for(int i=0;i<p.size();i++){
		ans=(ans+(D*p[i])%mod)%mod;
		D=(D*x)%mod;
	}
	return ans;
}
template <unsigned int mod = 998244353>
std::vector<long long> differential_Polynomial(std::vector<long long> p){
	int N=p.size();
	std::vector<long long> r(N);
	for(int i=1;i<N;i++){
		r[i-1]=((long long)(i)*p[i])%mod;
	}
	return r;
}

template <unsigned int mod = 998244353>
std::vector<long long> Integral_Polynomial(std::vector<long long> p){
	int N=p.size();
	std::vector<long long> r(1+N);
	std::vector<long long> rev(N+1,1);
	for(int i=0;i<N;i++){
		if(i+1>1){
			rev[i+1]=(mod-((mod/(i+1))*rev[mod%(i+1)])%mod)%mod;
		}
		r[i+1]=(rev[i+1]*p[i])%mod;
	}
	return r;
}


template <class T>
std::vector<T> slice_vec(std::vector<T> &p,int S){
	if(S>=(int)(p.size())) return p;
	std::vector<T> r(S);
	for(int i=0;i<S;i++) r[i]=p[i];
	return r;
}
// return f^{-1} mod x^{L}
// https://judge.yosupo.jp/submission/79004
template <unsigned int mod = 998244353>
std::vector<long long> inv_FPS(int N,int L,std::vector<long long> &p){
	assert((int)p.size()==N);
	assert(0<N);
	assert(p[0]%mod!=0);
	std::vector<long long> q={1},tmp,tmp2;
	long long D=p[0];
	long long C=mod-2;
	while(C){
		if(C&1){
			q[0]=(q[0]*D)%mod;
		}
		C>>=1;
		D=(D*D)%mod;
	}
	int S=1;
	while(S<L){
		S*=2;
		tmp.assign(S,0);
		for(int i=0;i<std::min((int)(p.size()),S);i++) tmp[i]=p[i];
		tmp2=convolution<mod>(tmp,convolution<mod>(q,q));
		for(int i=0;i<S;i++){
			if(i*2<S) tmp[i]=(2ll*q[i]-tmp2[i]+mod)%mod;
			else tmp[i]=(-tmp2[i]+mod)%mod;
		}
		swap(tmp,q);
	}
	std::vector<long long> ans(S);
	for(int i=0;i<S;i++) ans[i]=q[i];
	return ans;
}
// return log f(x)
// https://judge.yosupo.jp/submission/79008
template <unsigned int mod = 998244353>
std::vector<long long> log_FPS(int N,int L,std::vector<long long> &p){
	assert(p[0]==1);
	auto tmp=convolution<mod>(differential_Polynomial<mod>(p),inv_FPS<mod>(N,L,p));
	auto tmp3=Integral_Polynomial<mod>(tmp);
	return slice_vec(tmp3,L);
}
// return e^{f(x)}
template <unsigned int mod = 998244353>
std::vector<long long> exp_FPS(int N,int L,std::vector<long long> &p){
	assert((int)p.size()==N);
	assert(0<N);
	assert(p[0]%mod==0);
	std::vector<long long> q={1},tmp,tmp2,tmp3;
	int S=1;
	while(S<L){
		S*=2;
		tmp=slice_vec(p,S);
        tmp2=log_FPS<mod>(S/2,S,q);
        tmp3=sub_Polynomial<mod>(tmp,tmp2);
        tmp3[0]++;
        tmp=convolution<mod>(q,tmp3);
        for(int i=0;i<S;i++){
            if(i==(int)(q.size())) q.push_back(tmp[i]);
            else q[i]=tmp[i];
        }
	}
	std::vector<long long> ans(S);
	for(int i=0;i<S;i++) ans[i]=q[i];
	return ans;
}

//if all zero:
// return {0}
std::vector<long long> zero_cut(std::vector<long long> &p){
    int ind=0;
    for(int i=0;i<(int)(p.size());i++){
        if(p[i]!=0) ind=i;
    }
    return slice_vec(p,ind+1);
}
//return {a,b} (p=aq+b)
//https://judge.yosupo.jp/submission/79020
template <unsigned int mod = 998244353>
std::pair<std::vector<long long>,std::vector<long long>> div_FPS(std::vector<long long> &p,std::vector<long long> &q){
    int N=p.size(),M=q.size();
	if(N<M){
        return {{0},p};
    }
    auto f=p,g=q;
    std::reverse(f.begin(),f.end());
    std::reverse(g.begin(),g.end());
    auto tmp=convolution<mod>(f,inv_FPS(M,N-M+1,g));
    auto ans1=slice_vec(tmp,N-M+1);
    std::reverse(ans1.begin(),ans1.end());
    tmp=convolution(ans1,q);
    std::vector<long long> ans2(M-1);
    for(int i=0;i<M-1;i++) ans2[i]=(p[i]-tmp[i]+mod)%mod;
    return std::make_pair(zero_cut(ans1),zero_cut(ans2));
}
//return [f(p[0]),f(p[1])...f(p[M-1])]
//https://judge.yosupo.jp/submission/79035
template <unsigned int mod = 998244353>
std::vector<long long> Multipoint_Evaluation(std::vector<long long> f,std::vector<long long>p){
    int M=p.size();
	if(M==0){
		return {};
	}
    std::vector<int> size={M};
    int ind=0;
    while(size[ind]!=1){
        size.push_back((size[ind]+1)/2);
        ind++;
    }
    ind++;
    std::vector<std::vector<std::vector<long long>>> divisor(ind),remain(ind);
    for(int i=0;i<ind;i++){
        divisor[i].resize(size[i]);
        if(i==0){
            for(int j=0;j<M;j++){
                divisor[i][j]={mod-p[j],1};
            }
        }else{
            for(int j=0;j<size[i];j++){
                if(j!=size[i]-1||size[i-1]%2==0){
                    divisor[i][j]=convolution<mod>(divisor[i-1][j*2],divisor[i-1][j*2+1]);
                }else{
                    divisor[i][j]=divisor[i-1][size[i-1]-1];
                }
            }
        }
    }
    for(int i=ind-1;i>=0;i--){
        remain[i].resize(size[i]);
        if(i==ind-1){
            remain[i][0]=div_FPS<mod>(f,divisor[ind-1][0]).second;
        }else{
            for(int j=0;j<size[i];j++){
                if(j!=size[i]-1||size[i]%2==0){
                    remain[i][j]=div_FPS(remain[i+1][j/2],divisor[i][j]).second;
                }else{
                    remain[i][j]=remain[i+1][j/2];
                }
            }
        }
    }
    std::vector<long long> ans(M);
    for(int i=0;i<M;i++) ans[i]=remain[0][i][0];
    return ans;
}

template <unsigned int mod = 998244353>
std::vector<long long> multiplication_FPS(std::vector<std::vector<long long>> &p){
    std::queue<std::vector<long long>> pq;
    int N=p.size();
    for(int i=0;i<N;i++) pq.push(p[i]);
    for(int i=1;i<N;i++){
        auto l=pq.front();
        pq.pop();
        auto r=pq.front();
        pq.pop();
        pq.push(convolution<mod>(l,r));
    }
    return pq.front();
}
struct frac_fps{
    std::vector<long long> ch;
    std::vector<long long> mo;
};
template <unsigned int mod = 998244353>
frac_fps add_frac_fps(frac_fps &l,frac_fps &r){
    auto tmp1=convolution<mod>(l.ch,r.mo);
    auto tmp2=convolution<mod>(l.mo,r.ch);
    return {add_Polynomial<mod>(tmp1,tmp2),convolution<mod>(l.mo,r.mo)};
}
template <unsigned int mod = 998244353>
std::vector<long long> Polynomial_Interpolation(std::vector<long long> &x,std::vector<long long> &y){
    int N=x.size();
    assert(x.size()==y.size());
    std::vector<std::vector<long long>> p(N);
    for(int i=0;i<N;i++){
        p[i]={(mod-x[i])%mod,1};
    }
    auto tmp1=multiplication_FPS<mod>(p);
    auto div=differential_Polynomial<mod>(tmp1);
    auto val=Multipoint_Evaluation<mod>(div,x);
    std::queue<frac_fps> q;
    for(int i=0;i<N;i++) q.push({{y[i]},{(mod-(val[i]*x[i])%mod)%mod,val[i]}});
    for(int i=1;i<N;i++){
        frac_fps l=q.front();
        q.pop();
        frac_fps r=q.front();
        q.pop();
        q.push(add_frac_fps<mod>(l,r));
    }
    long long D=1;
    auto ans=q.front().ch;
    for(int i=0;i<N;i++){
        D=(D*val[i])%mod;
    }
    D=rev(D,mod);
    for(int i=0;i<N;i++) ans[i]=(ans[i]*D)%mod;
    return ans;
}
}


void solve();

// 僕なんか
int main() {
	int t=1;
	//cin>>t;
	rep(i,t) solve();
}

void solve(){
	int N,K;
	cin>>N>>K;
	vector<ll> E(N+1),F(N+1);
	rep(i,N) cin>>E[i+1],F[i+1]=(mod-E[i+1])%mod;
	F[0]=1;
	auto ans0=po167::inv_FPS(1+N,N+167,F);
	ans0[0]=0;
	vector<ll> X,Y;
	auto _E=po167::differential_Polynomial(E);
	rep(i,N){
		if(_E[i]!=0){
			X.resize(N+1-i);
			Y.resize(N-i);
			rep(j,N-i){
				Y[j]=_E[j+i];
				X[j+1]=E[j+i+1];
			}
			break;
		}
	}
	auto Y_inv=po167::inv_FPS((int)(Y).size(),N+3,Y);
	while(K>0){
		ans0=po167::differential_Polynomial(ans0);
		ans0=convolution(ans0,X);
		ans0.resize(N+167);
		ans0=convolution(ans0,Y_inv);
		ans0.resize(N+167);
		K--;
		cout<<"\n";
	}
	X.erase(X.begin());
	auto X_inv=po167::inv_FPS(X.size(),N+167,X);
	while(K<0){
		ans0.erase(ans0.begin());
		ans0=convolution(ans0,X_inv);
		ans0.resize(N+167);
		ans0=convolution(ans0,Y);
		ans0.resize(N+167);
		ans0=po167::Integral_Polynomial(ans0);
		K++;
	}
	rep(i,N){
		if(i!=0) cout<<" ";
		cout<<ans0[i+1];
	}
	cout<<"\n";
}
0