結果
| 問題 |
No.1985 [Cherry 4th Tune] Early Summer Rain
|
| コンテスト | |
| ユーザー |
👑  potato167
|
| 提出日時 | 2022-05-27 02:32:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,957 bytes |
| コンパイル時間 | 3,903 ms |
| コンパイル使用メモリ | 241,820 KB |
| 最終ジャッジ日時 | 2025-01-29 15:27:48 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 1 |
| other | AC * 19 WA * 27 |
ソースコード
#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";
}