#606580 (C++14) No.1356 Split Tile2

提出ソース
結果

問題	No.1356 Split Tile2
コンテスト
ユーザー	hos.lyric
提出日時	2021-01-17 14:08:12
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	126 ms / 2,000 ms
コード長	8,727 bytes
コンパイル時間	1,836 ms
コンパイル使用メモリ	179,240 KB
実行使用メモリ	65,020 KB
最終ジャッジ日時	2024-11-29 15:25:53
合計ジャッジ時間	5,481 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 31
権限があれば一括ダウンロードができます
ソースコード

raw source code
// https://judge.yosupo.jp/submission/958
#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
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

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<<"}";
}

using uint=unsigned;
using ull=unsigned long long;

const uint mod=998244353;
//const uint mod=1000000007;
//uint mod=1;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint& operator+=(const mint&rhs){return s(v+rhs.v);}
	mint&operator-=(const mint&rhs){return s(v+mod-rhs.v);}
	mint&operator*=(const mint&rhs){
		v=ull(v)*rhs.v%mod;
		return *this;
	}
	mint&operator/=(const mint&rhs){return *this*=rhs.inv();}
	mint operator+(const mint&rhs)const{return mint(*this)+=rhs;}
	mint operator-(const mint&rhs)const{return mint(*this)-=rhs;}
	mint operator*(const mint&rhs)const{return mint(*this)*=rhs;}
	mint operator/(const mint&rhs)const{return mint(*this)/=rhs;}
	mint pow(int n)const{
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
	/*mint inv()const{
		int x,y;
		int g=extgcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return mint(x);
	}*/
	friend ostream& operator<<(ostream&os,const mint&m){
		return os<<m.v;
	}
	bool operator<(const mint&r)const{return v<r.v;}
	bool operator==(const mint&r)const{return v==r.v;}
};

const int vmax=(1<<21)+10;
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 fact[n]*finv[n-k]*finv[k];
}
mint binom(int a,int b){
	return fact[a+b]*finv[a]*finv[b];
}
mint catalan(int n){
	return binom(n,n)-(n-1>=0?binom(n-1,n+1):0);
}

#define USE_FMT
//998244353
const mint prim_root=3;

/*
//in-place fft
//size of input must be a power of 2
void inplace_fmt(vector<mint>&f,const bool inv){
	const int n=f.size();
	const mint root=inv?prim_root.inv():prim_root;
	vc<mint> g(n);
	for(int b=n/2;b>=1;b/=2){
		mint w=root.pow((mint::base-1)/(n/b)),p=1;
		for(int i=0;i<n;i+=b*2){
			rep(j,b){
				f[i+j+b]*=p;
				g[i/2+j]=f[i+j]+f[i+b+j];
				g[n/2+i/2+j]=f[i+j]-f[i+b+j];
			}
			p*=w;
		}
		swap(f,g);
	}
	if(inv)rep(i,n)
		f[i]*=inv[n];
}*/

static const int LG=21;
mint roots[1<<(LG+1)],iroots[1<<(LG+1)];
struct PrepareRoots{
	PrepareRoots(){
		rep(w,LG+1){
			const int s=(1<<w)-1;
			const mint g=prim_root.pow((mod-1)/(1<<w)),ig=g.inv();
			mint p=1,ip=1;
			rep(i,1<<w){
				roots[s+i]=p;p*=g;
				iroots[s+i]=ip;ip*=ig;
			}
		}
	}
} PrepareRootsDummy;

void broken_fmt(vc<mint>&f){
	const int n=f.size();
	for(int b=n/2;b>=1;b/=2){
		for(int i=0;i<n;i+=b*2){
			rep(j,b){
				mint tmp=f[i+j]-f[i+j+b];
				f[i+j]+=f[i+j+b];
				f[i+j+b]=tmp*roots[b*2-1+j];
			}
		}
	}
}

void broken_ifmt(vc<mint>&f){
	const int n=f.size();
	for(int b=1;b<=n/2;b*=2){
		for(int i=0;i<n;i+=b*2){
			rep(j,b){
				f[i+j+b]*=iroots[b*2-1+j];
				mint tmp=f[i+j]-f[i+j+b];
				f[i+j]+=f[i+j+b];
				f[i+j+b]=tmp;
			}
		}
	}
	rep(i,n)
		f[i]*=invs[n];
}

void inplace_fmt(vector<mint>&f,const bool i){
	if(!i)broken_fmt(f);
	else broken_ifmt(f);
}

vc<mint> multiply(vc<mint> x,vc<mint> y,bool same=false){
	int n=x.size()+y.size()-1;
	int s=1;
	while(s<n)s*=2;
	x.resize(s);inplace_fmt(x,false);
	if(!same){
		y.resize(s);inplace_fmt(y,false);
	}else
		y=x;
	rep(i,s)
		x[i]*=y[i];
	inplace_fmt(x,true);x.resize(n);
	return x;
}

template<class D>
struct Poly:public vc<D>{
	template<class...Args>
	Poly(Args...args):vc<D>(args...){}
	Poly(initializer_list<D>init):vc<D>(all(init)){}
	int size()const{
		return vc<D>::size();
	}
	void ups(int s){
		if(size()<s)this->resize(s,0);
	}
	Poly low(int s)const{
		return Poly(this->bg,this->bg+min(max(s,int(1)),size()));
	}
	Poly rev()const{
		auto r=*this;
		reverse(all(r));
		return r;
	}
	Poly& operator+=(const Poly&r){
		ups(r.size());
		rep(i,r.size())
			(*this)[i]+=r[i];
		return *this;
	}
	Poly& operator-=(const Poly&r){
		ups(r.size());
		rep(i,r.size())
			(*this)[i]-=r[i];
		return *this;
	}
	template<class T>
	Poly& operator*=(T t){
		for(auto&v:*this)
			v*=t;
		return *this;
	}
	Poly& operator*=(const Poly&r){
		return *this=multiply(*this,r);
	}
	Poly square()const{
		return multiply(*this,*this,true);
	}
	#ifndef USE_FMT
	Poly inv(int s)const{
		Poly r{D(1)/(*this)[0]};
		for(int n=1;n<s;n*=2)
			r=r*2-(r.square()*low(2*n)).low(2*n);
		return r.low(s);
	}
	#else
	Poly inv(int s)const{
		Poly r{D(1)/(*this)[0]};
		for(int n=1;n<s;n*=2){
			r.resize(n*4);
			inplace_fmt(r,false);
			vc<D> f=low(2*n);
			f.resize(n*4);
			inplace_fmt(f,false);
			rep(i,n*4)
				r[i]=r[i]*2-r[i]*r[i]*f[i];
			inplace_fmt(r,true);
			r.resize(2*n);
		}
		return r.low(s);
	}
	#endif
	template<class T>
	Poly& operator/=(T t){
		return *this*=D(1)/D(t);
	}
	Poly quotient(const Poly&r,const Poly&rri)const{
		int m=r.size();
		assert(r[m-1].v);
		int n=size();
		int s=n-m+1;
		if(s<=0) return {0};
		return (rev().low(s)*rri.low(s)).low(s).rev();
	}
	Poly& operator/=(const Poly&r){
		return *this=quotient(r,r.rev().inv(max(size()-r.size(),int(0))+1));
	}
	Poly& operator%=(const Poly&r){
		*this-=*this/r*r;
		return *this=low(r.size()-1);
	}
	Poly operator+(const Poly&r)const{return Poly(*this)+=r;}
	Poly operator-(const Poly&r)const{return Poly(*this)-=r;}
	template<class T>
	Poly operator*(T t)const{return Poly(*this)*=t;}
	Poly operator*(const Poly&r)const{return Poly(*this)*=r;}
	template<class T>
	Poly operator/(T t)const{return Poly(*this)/=t;}
	Poly operator/(const Poly&r)const{return Poly(*this)/=r;}
	Poly operator%(const Poly&r)const{return Poly(*this)%=r;}
	Poly dif()const{
		Poly r(max(int(0),size()-1));
		rep(i,r.size())
			r[i]=(*this)[i+1]*(i+1);
		return r;
	}
	Poly inte()const{
		Poly r(size()+1,0);
		rep(i,size())
			r[i+1]=(*this)[i]*invs[i+1];
		return r;
	}
	//opencupXvcIII GP of Peterhof H
	Poly log(int s)const{
		return (low(s).dif()*inv(s-1)).low(s-1).inte();
	}
	//Petrozavodsk 2019w Day1 G
	//yosupo judge
	Poly exp(int s)const{
		return exp2(s).a;
	}
	//2つほしいときはコメントアウトの位置ずらす
	pair<Poly,Poly> exp2(int s)const{
		assert((*this)[0]==mint(0));
		Poly f{1},g{1};
		for(int n=1;;n*=2){
			if(n>=s)break;
			g=g*2-(g.square()*f).low(n);
			//if(n>=s)break;
			Poly q=low(n).dif();
			q=q+g*(f.dif()-f*q).low(2*n-1);
			f=f+(f*(low(2*n)-q.inte())).low(2*n);
		}
		return make_pair(f.low(s),g.low(s));
	}
	//CF250 E
	Poly sqrt(int s)const{
		assert((*this)[0]==1);
		Poly r{1};
		for(int n=1;n<s;n*=2)
			r=(r+(r.inv(n*2)*low(n*2)).low(n*2))*inv[2];
		return r.low(s);
	}
	pair<Poly,Poly> divide(const Poly&r,const Poly&rri)const{
		Poly a=quotient(r,rri);
		Poly b=*this-a*r;
		return make_pair(a,b.low(r.size()-1));
	}
	//Yukicoder No.215
	Poly pow_mod(int n,const Poly&r)const{
		Poly rri=r.rev().inv(r.size());
		Poly cur{1},x=*this%r;
		while(n){
			if(n%2)
				cur=(cur*x).divide(r,rri).b;
			x=(x*x).divide(r,rri).b;
			n/=2;
		}
		return cur;
	}
	D eval(D x)const{
		D r=0,w=1;
		for(auto v:*this){
			r+=w*v;
			w*=x;
		}
		return r;
	}
};

/*
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	initfact();
	
	int n;cin>>n;
	n++;
	Poly<mint> f(n);
	rep(i,n)
		f[i]=finv[i+1];
	auto g=f.inv(n);
	rep(i,n)
		cout<<g[i]*fact[i]<<(i<n-1?" ":"\n");
}
*/

////////

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	initfact();
  
  ll N;
  for (; ~scanf("%lld", &N); ) {
    Poly<mint> g(N + 1), q(N + 1);
    for (int i = 0; i <= N; ++i) {
      g[i] = fact[i + 1] + 1;
      q[i] = fact[i + 1];
    }
    g[0] = 1;
    const auto h = g * q.inv(N + 1);
    const mint ans = mint(1) - h[N];
    printf("%u\n", ans.v);
  }
  return 0;
}
yukicoder

結果

ソースコード
