Submission #45302403

---

Source Code Expand

#ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){	return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){	os<<"{";	for(auto e:v)os<<e<<",";	return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){	os<<t<<" ";	dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){	return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){	if(i)os<<",";	os<<get<i>(t);	print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){	os<<"{";	print_tuple<0,tuple<Args...>,Args...>(os,t);	return os<<"}"; } ll read(){	ll i;	cin>>i;	return i; } vi readvi(int n,int off=0){	vi v(n);	rep(i,n)v[i]=read()+off;	return v; } pi readpi(int off=0){	int a,b;cin>>a>>b;	return pi(a+off,b+off); } template<class t> void print_single(t x,int suc=1){	cout<<x;	if(suc==1)	cout<<"\n";	if(suc==2)	cout<<" "; } template<class t,class u> void print_single(const pair<t,u>&p,int suc=1){	print_single(p.a,2);	print_single(p.b,suc); } template<class T> void print_single(const vector<T>&v,int suc=1){	rep(i,v.size())	print_single(v[i],i==int(v.size())-1?suc:2); } template<class T> void print_offset(const vector<T>&v,ll off,int suc=1){	rep(i,v.size())	print_single(v[i]+off,i==int(v.size())-1?suc:2); } template<class T,size_t N> void print_single(const array<T,N>&v,int suc=1){	rep(i,N)	print_single(v[i],i==int(N)-1?suc:2); } template<class T> void print(const T&t){	print_single(t); } template<class T,class ...Args> void print(const T&t,const Args&...args){	print_single(t,2);	print(args...); } string readString(){	string s;	cin>>s;	return s; } template<class T> T sq(const T& t){	return t*t; } void YES(bool ex=true){	cout<<"YES\n";	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } void NO(bool ex=true){	cout<<"NO\n";	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } void Yes(bool ex=true){	cout<<"Yes\n";	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } void No(bool ex=true){	cout<<"No\n";	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } //#define CAPITAL /* void yes(bool ex=true){	#ifdef CAPITAL	cout<<"YES"<<"\n";	#else	cout<<"Yes"<<"\n";	#endif	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } void no(bool ex=true){	#ifdef CAPITAL	cout<<"NO"<<"\n";	#else	cout<<"No"<<"\n";	#endif	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif }*/ void possible(bool ex=true){	#ifdef CAPITAL	cout<<"POSSIBLE"<<"\n";	#else	cout<<"Possible"<<"\n";	#endif	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } void impossible(bool ex=true){	#ifdef CAPITAL	cout<<"IMPOSSIBLE"<<"\n";	#else	cout<<"Impossible"<<"\n";	#endif	if(ex)exit(0);	#ifdef LOCAL	cout.flush();	#endif } constexpr ll ten(int n){	return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){	return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){	return t==0?-1:63-__builtin_clzll(t); } int topbit(ull t){	return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){	return a==0?32:__builtin_ctz(a); } int botbit(ll a){	return a==0?64:__builtin_ctzll(a); } int botbit(ull a){	return a==0?64:__builtin_ctzll(a); } int popcount(signed t){	return __builtin_popcount(t); } int popcount(ll t){	return __builtin_popcountll(t); } int popcount(ull t){	return __builtin_popcountll(t); } int bitparity(ll t){	return __builtin_parityll(t); } bool ispow2(int i){	return i&&(i&-i)==i; } ll mask(int i){	return (ll(1)<<i)-1; } ull umask(int i){	return (ull(1)<<i)-1; } ll minp2(ll n){	if(n<=1)return 1;	else return ll(1)<<(topbit(n-1)+1); } bool inc(int a,int b,int c){	return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){	sort(all(v));	v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r]	//#ifdef LOCAL	static mt19937_64 gen;	/*#else	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());	#endif*/	return uniform_int_distribution<ll>(l, r)(gen); } ll rand_int(ll k){ //[0,k)	return rand_int(0,k-1); } template<class t> void myshuffle(vc<t>&a){	rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){	return lower_bound(all(v),a)-v.bg; } template<class t> bool bis(const vc<t>&v,const t&a){	return binary_search(all(v),a); } vvc<int> readGraph(int n,int m){	vvc<int> g(n);	rep(i,m){	int a,b;	cin>>a>>b;	//sc.read(a,b);	a--;b--;	g[a].pb(b);	g[b].pb(a);	}	return g; } vvc<int> readTree(int n){	return readGraph(n,n-1); } template<class t> vc<t> presum(const vc<t>&a){	vc<t> s(si(a)+1);	rep(i,si(a))s[i+1]=s[i]+a[i];	return s; } vc<ll> presum(const vi&a){	vc<ll> s(si(a)+1);	rep(i,si(a))s[i+1]=s[i]+a[i];	return s; } //BIT で数列を管理するときに使う (CF850C) template<class t> vc<t> predif(vc<t> a){	gnr(i,1,si(a))a[i]-=a[i-1];	return a; } template<class t> vvc<ll> imos(const vvc<t>&a){	int n=si(a),m=si(a[0]);	vvc<ll> b(n+1,vc<ll>(m+1));	rep(i,n)rep(j,m)	b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];	return b; } //verify してないや void transvvc(int&n,int&m){	swap(n,m); } template<class t,class... Args> void transvvc(int&n,int&m,vvc<t>&a,Args&...args){	assert(si(a)==n);	vvc<t> b(m,vi(n));	rep(i,n){	assert(si(a[i])==m);	rep(j,m)b[j][i]=a[i][j];	}	a.swap(b);	transvvc(n,m,args...); } //CF854E void rotvvc(int&n,int&m){	swap(n,m); } template<class t,class... Args> void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){	assert(si(a)==n);	vvc<t> b(m,vi(n));	rep(i,n){	assert(si(a[i])==m);	rep(j,m)b[m-1-j][i]=a[i][j];	}	a.swap(b);	rotvvc(n,m,args...); } //ソートして i 番目が idx[i] //CF850C template<class t> vi sortidx(const vc<t>&a){	int n=si(a);	vi idx(n);iota(all(idx),0);	sort(all(idx),[&](int i,int j){return a[i]<a[j];});	return idx; } //vs[i]=a[idx[i]] //例えば sortidx で得た idx を使えば単にソート列になって返ってくる //CF850C template<class t> vc<t> a_idx(const vc<t>&a,const vi&idx){	int n=si(a);	assert(si(idx)==n);	vc<t> vs(n);	rep(i,n)vs[i]=a[idx[i]];	return vs; } //CF850C vi invperm(const vi&p){	int n=si(p);	vi q(n);	rep(i,n)q[p[i]]=i;	return q; } template<class t,class s=t> s SUM(const vc<t>&a){	return accumulate(all(a),s(0)); } template<class t> t MAX(const vc<t>&a){	return *max_element(all(a)); } template<class t> t MIN(const vc<t>&a){	return *min_element(all(a)); } template<class t> pair<t,int> MINi(const vc<t>&a){	auto itr=min_element(all(a));	return mp(*itr,itr-a.bg); } template<class t,class u> pair<t,u> operator+(const pair<t,u>&a,const pair<t,u>&b){	return mp(a.a+b.a,a.b+b.b); } vi vid(int n){	vi res(n);iota(all(res),0);	return res; } template<class S> S revv(S s){	reverse(all(s));	return s; } pi operator+(pi a,pi b){return pi(a.a+b.a,a.b+b.b);} template<class t> t gpp(vc<t>&vs){	assert(si(vs));	t res=move(vs.back());	vs.pop_back();	return res; } template<class t> void pb(vc<t>&a,const vc<t>&b){	a.insert(a.ed,all(b)); } template<class t> vc<t> cat(vc<t> a,const vc<t>&b){	pb(a,b);	return a; } template<class t,class u> vc<t>& operator+=(vc<t>&a,u x){	for(auto&v:a)v+=x;	return a; } template<class t,class u> vc<t> operator+(vc<t> a,u x){	return a+=x; } template<class t,class u> vc<t>& operator-=(vc<t>&a,u x){	for(auto&v:a)v-=x;	return a; } template<class t,class u> vc<t>& operator-(vc<t> a,u x){	return a-=x; } //mint107 は verify してねえ //#define DYNAMIC_MOD struct modinfo{uint mod,root; #ifdef DYNAMIC_MOD constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);} ull im; constexpr void set_mod(uint m){	mod=m;	im=ull(-1)/m+1; } uint product(uint a,uint b)const{	ull z=ull(a)*b;	uint x=((unsigned __int128)z*im)>>64;	uint v=uint(z)-x*mod;	return v<mod?v:v+mod; } #endif }; template<modinfo const&ref> struct modular{	static constexpr uint const &mod=ref.mod;	static modular root(){return modular(ref.root);}	uint v;	//modular(initializer_list<uint>ls):v(*ls.bg){}	modular(ll vv=0){s(vv%mod+mod);}	modular& s(uint vv){	v=vv<mod?vv:vv-mod;	return *this;	}	modular operator-()const{return modular()-*this;}	modular& operator+=(const modular&rhs){return s(v+rhs.v);}	modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);}	modular&operator*=(const modular&rhs){	#ifndef DYNAMIC_MOD	v=ull(v)*rhs.v%mod;	#else	v=ref.product(v,rhs.v);	#endif	return *this;	}	modular&operator/=(const modular&rhs){return *this*=rhs.inv();}	modular operator+(const modular&rhs)const{return modular(*this)+=rhs;}	modular operator-(const modular&rhs)const{return modular(*this)-=rhs;}	modular operator*(const modular&rhs)const{return modular(*this)*=rhs;}	modular operator/(const modular&rhs)const{return modular(*this)/=rhs;}	modular pow(ll n)const{	if(n<0)return inv().pow(-n);	modular res(1),x(*this);	while(n){	if(n&1)res*=x;	x*=x;	n>>=1;	}	return res;	}	modular inv()const{return pow(mod-2);}	/*modular inv()const{	int x,y;	int g=extgcd<ll>(v,mod,x,y);	assert(g==1);	if(x<0)x+=mod;	return modular(x);	}*/	friend modular operator+(ll x,const modular&y){	return modular(x)+y;	}	friend modular operator-(ll x,const modular&y){	return modular(x)-y;	}	friend modular operator*(ll x,const modular&y){	return modular(x)*y;	}	friend modular operator/(ll x,const modular&y){	return modular(x)/y;	}	friend ostream& operator<<(ostream&os,const modular&m){	return os<<m.v;	}	friend istream& operator>>(istream&is,modular&m){	ll x;is>>x;	m=modular(x);	return is;	}	bool operator<(const modular&r)const{return v<r.v;}	bool operator==(const modular&r)const{return v==r.v;}	bool operator!=(const modular&r)const{return v!=r.v;}	explicit operator bool()const{	return v;	} }; #ifndef DYNAMIC_MOD extern constexpr modinfo base{998244353,3}; //extern constexpr modinfo base{1000000007,0}; //extern constexpr modinfo base{2147483579,0};//2^31 未満の最大の安全素数 //modinfo base{1,0}; #ifdef USE_GOOD_MOD static_assert(base.mod==998244353); #endif #else modinfo base(1,0); extern constexpr modinfo base107(1000000007,0); using mint107=modular<base107>; #endif using mint=modular<base>; mint parity(int i){	return i%2==0?1:-1; } #ifdef LOCAL const int vmax=10010; #else const int vmax=(1<<21)+10; #endif mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){	fact[0]=1;	rng(i,1,vmax){	fact[i]=fact[i-1]*i;	}	finv[vmax-1]=fact[vmax-1].inv();	for(int i=vmax-2;i>=0;i--){	finv[i]=finv[i+1]*(i+1);	}	for(int i=vmax-1;i>=1;i--){	invs[i]=finv[i]*fact[i-1];	} } mint choose(int n,int k){	return inc(0,k,n)?fact[n]*finv[n-k]*finv[k]:0; } mint binom(int a,int b){	return 0<=a&&0<=b?fact[a+b]*finv[a]*finv[b]:0; } mint catalan(int n){	return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } //対角線を超えず (x,y) に至る方法の数 mint catalan(int x,int y){	return binom(x,y)-binom(x+1,y-1); } /* const int vmax=610; mint fact[vmax+1],binbuf[vmax+1][vmax+1]; mint choose(int n,int k){	return 0<=k&&k<=n?binbuf[n-k][k]:0; } mint binom(int a,int b){	return 0<=a&&0<=b?binbuf[a][b]:0; } void initfact(int n){	fact[0]=1;	rep(i,n)fact[i+1]=fact[i]*(i+1);	rep(i,n+1)rep(j,n+1){	if(i==0&&j==0){	binbuf[i][j]=1;	}else{	binbuf[i][j]=0;	if(i)binbuf[i][j]+=binbuf[i-1][j];	if(j)binbuf[i][j]+=binbuf[i][j-1];	}	} } */ mint p2[vmax],p2inv[vmax]; void initp2(){	p2[0]=1;	rep(i,vmax-1)p2[i+1]=p2[i]*2;	p2inv[vmax-1]=p2[vmax-1].inv();	per(i,vmax-1)p2inv[i]=p2inv[i+1]*2; } bool dbg=false; mint sub(int x,int y){	assert(x<=y);	mint res=binom(x,y);	if(x>0)res-=binom(x-1,y+1);	return res; } vc<mint> getls(int n,int m,int l,int r){	vc<mint> res(n+1);	auto work=[&](int top,mint w){	mint cur=0;	rep(i,n+1){	if(i==0)rep(j,top)cur+=binom(n,m-j);	res[i]+=cur*w;	if(i<n){	if(i+top)cur-=binom(i+1,i+top-1)*binom(n-i,m-(i+top));	cur+=binom(i+1,i+top)*binom(n-i-1,m-(i+top));	}	}	};	work(l,-1);	work(r,1);	return res; } void slv(){	int n,m;cin>>n>>m;	assert(n<m);	vc<mint> res(n);	{	vc<mint> add(n+1);	add[0]+=sub(n,m);	if(n<m){	rep(x,2)rep(y,2){	auto ls=getls(n-x-y,m-1+x+y,2*x,(m-n)+2*x);	rep(i,si(ls))add[x+i]+=ls[i]*parity(x+y);	}	}	vc<mint> sum(n+2);	rep(i,n+1){	sum[i]+=add[i];	sum[n-i+1]-=add[i];	}	rep(i,n+1)sum[i+1]+=sum[i];	sum.resize(n+1);	per(i,n)sum[i]+=sum[i+1];	rep(i,n)res[i]+=sum[n-i];	}	{	vc<mint> a(n+1);	rng(len,1,n){	mint w=binom(n-len,m-len-1);	if(n<m)w-=sub(n-len,m-len-1);	a[len]+=w*catalan(len);	}	per(i,n)a[i]+=a[i+1];	per(i,n)a[i]+=a[i+1];	rep(i,n)res[i]+=a[n-i];	rep(i,n)res[i]-=a[i+1];	}	rep(i,n)print(res[i]-binom(n,m)); } signed main(){	cin.tie(0);	ios::sync_with_stdio(0);	cout<<fixed<<setprecision(20);	initfact();	if(dbg){	while(1)slv();	}else{	//int t;cin>>t;rep(_,t)	slv();	} } 

Submission Info

Judge Result