QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104339#4491. Find the Number of Paths2024zllAC ✓5068ms77304kbC++147.9kb2023-05-10 10:38:072023-05-10 10:38:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-10 10:38:11]
  • 评测
  • 测评结果：AC
  • 用时：5068ms
  • 内存：77304kb
查看
  • [2023-05-10 10:38:07]
  • 提交

answer

#include<algorithm>
#include<chrono>
#include<cstdio>
#include<random>
#include<functional>
#include<vector>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
typedef long long ll;
const int maxn=1<<20;
const ll P=998244353;
inline void qmod(int&x){
	x=x+((x>>31)&int(P));
}
inline void qmod(ll&x){
	x=x+((x>>63)&P);
}
template<typename T>
void swap(T&a,T&b){
	const T temp=a;
	a=b;
	b=temp;
}
ll qpow(ll a,int x=P-2){
	ll answer=1;
	while(x){
		if(x&1)answer=answer*a%P;
		a=a*a%P;
		x>>=1;
	}
	return answer;
}
inline int get_n(const int deg){
	int n=1;
	while(n<=deg)n<<=1;
	return n;
}
const ll PR=3,invPR=qpow(PR),inv_2=qpow(2);
int fac[maxn+1],inv[maxn+1],fac_inv[maxn+1];
struct ARR{
	ARR(){
		fac[0]=1;
		for(int i=1;i<=maxn;i++)fac[i]=(ll)fac[i-1]*i%P;
		inv[1]=1;
		fac_inv[0]=fac_inv[1]=1;
		for(int i=2;i<=maxn;i++){
			inv[i]=ll(P-P/i)*inv[P%i]%P;
			fac_inv[i]=(ll)fac_inv[i-1]*inv[i]%P;
		}
	}
}arr;
template<const int size>
struct Transform{
	private:
		std::vector<int>tr;
	public:
		void init(const int n){
			if((int)tr.size()==n)return;
			tr.resize(n);
			for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
		}
		int operator[](const int x)const{
			return tr[x];
		}
};
Transform<maxn<<1>tr;
template<typename T_store,typename T_calc>
struct Poly{
	private:
		std::vector<T_store>v;
	public:
		Poly<T_store,T_calc>(){}
		Poly<T_store,T_calc>(const T_store val){
			v.emplace_back(val);
		}
		void clear(){
			v.clear();
		}
		int&operator[](const T_store x){
			return v[x];
		}
		int deg(){
			return(int)v.size()-1;
		}
		void set_deg(const int n){
			v.resize(n+1);
		}
		friend void reverse(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			const int n=F.deg();
			G.set_deg(n);
			for(int i=0;i<=n;i++)G.v[n-i]=F[i];
		}
		void reverse_itself(){
			std::reverse(v.begin(),v.end());
		}
		void ntt(const bool type,const int n){
			tr.init(n);
			v.resize(n);
			for(int i=0;i<n;i++)
				if(i<tr[i])
					swap(v[i],v[tr[i]]);
			for(int p=2;p<=n;p<<=1){
				const int len=p>>1;
				const T_calc tPR=qpow(type?PR:invPR,(P-1)/p);
				for(int k=0;k<n;k+=p){
					T_calc buf=1;
					for(int l=k;l<k+len;l++){
						const T_calc temp=buf*v[l+len]%P;
						qmod(v[l+len]=v[l]-temp);
						qmod(v[l]+=temp-P);
						buf=buf*tPR%P;
					}
				}
			}
		}
		friend Poly<T_store,T_calc>operator*(Poly<T_store,T_calc>&F,const T_calc G){
			Poly H;
			H.v.resize(F.v.size());
			for(int i=0;i<(int)F.v.size();i++)H.v[i]=F.v[i]*G%P;
			return H;
		}
		friend Poly<T_store,T_calc>operator+(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			Poly<T_store,T_calc>H;
			int len1=F.deg(),len2=G.deg();
			if(len1<len2){
				H.set_deg(len2);
				for(int i=0;i<=len1;i++)qmod(H.v[i]=F[i]+G[i]-P);
				for(int i=len1+1;i<=len2;i++)qmod(H.v[i]=-G[i]);
			}else{
				H.set_deg(len1);
				for(int i=0;i<=len2;i++)qmod(H.v[i]=F[i]+G[i]-P);
				for(int i=len2+1;i<=len1;i++)H.v[i]=F[i];
			}
			return H;
		}
		friend Poly<T_store,T_calc>operator-(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			Poly<T_store,T_calc>H;
			int len1=F.deg(),len2=G.deg();
			if(len1<len2){
				H.set_deg(len2);
				for(int i=0;i<=len1;i++)qmod(H.v[i]=F[i]-G[i]);
				for(int i=len1+1;i<=len2;i++)qmod(H.v[i]=-G[i]);
			}else{
				H.set_deg(len1);
				for(int i=0;i<=len2;i++)qmod(H.v[i]=F[i]-G[i]);
				for(int i=len2+1;i<=len1;i++)H.v[i]=F[i];
			}
			return H;
		}
		friend Poly<T_store,T_calc>operator*(Poly<T_store,T_calc>F,Poly<T_store,T_calc>G){
			const int len=F.deg()+G.deg(),n=get_n(len);
			F.ntt(true,n);
			G.ntt(true,n);
			Poly<T_store,T_calc>H;
			H.v.resize(n);
			for(int i=0;i<n;i++)H.v[i]=(T_calc)F.v[i]*G.v[i]%P;
			H.ntt(false,n);
			H.set_deg(len);
			return H*qpow(n);
		}
		friend Poly<T_store,T_calc>poly_multiply(Poly<T_store,T_calc>F,Poly<T_store,T_calc>G,std::function<T_store(T_store,T_store)>func){
			const int len=F.deg()+G.deg(),n=get_n(len);
			F.ntt(true,n);
			G.ntt(true,n);
			Poly<T_store,T_calc>H;
			H.v.resize(n);
			for(int i=0;i<n;i++)H.v[i]=func(F.v[i],G.v[i]);
			H.ntt(false,n);
			H.set_deg(len);
			return H*qpow(n);
		}
		friend Poly<T_store,T_calc>poly_multiply_reference(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G,std::function<T_store(T_store,T_store)>func){
			const int len=F.deg()+G.deg(),n=get_n(len);
			F.ntt(true,n);
			G.ntt(true,n);
			Poly<T_store,T_calc>H;
			H.v.resize(n);
			for(int i=0;i<n;i++)H.v[i]=func(F.v[i],G.v[i]);
			H.ntt(false,n);
			H.set_deg(len);
			return H*qpow(n);
		}
		friend void poly_inverse(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			const int len=F.deg(),n=get_n(len);
			F.v.resize(n<<1);
			G.v.clear();
			G.v.emplace_back(qpow(F[0]));
			Poly<T_store,T_calc>A,B;
			for(int l=1;l<=(len<<1);l<<=1){
				const int lim=l<<1;
				A.v.assign(F.v.begin(),F.v.begin()+l);
				B.v.assign(G.v.begin(),G.v.begin()+l);
				G=poly_multiply_reference(A,B,[](const T_store x,const T_store y){
					return T_store((P+2-(T_calc)x*y%P)*y%P);
				});
				for(int i=l;i<lim;i++)G.v[i]=0;
			}
			F.set_deg(len);
			G.set_deg(len);
		}
		friend void poly_derivation(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			const int n=F.deg();
			G.set_deg(n);
			for(int i=1;i<=n;i++)G.v[i-1]=(T_calc)F[i]*i%P;
			G.v[n]=0;
		}
		friend void poly_integral(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			const int n=F.deg();
			G.set_deg(n);
			for(int i=1;i<=n;i++)G.v[i]=(T_calc)F[i-1]*inv[i]%P;
			G.v[0]=0;
		}
		friend void poly_ln(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			Poly<T_store,T_calc>F_derivation,F_inv,G_derivation;
			poly_derivation(F,F_derivation);
			poly_inverse(F,F_inv);
			G_derivation=poly_multiply(F_derivation,F_inv,[](const T_store x,const T_store y){
				return T_store((T_calc)x*y%P);
			});
			G_derivation.set_deg(F.deg());
			poly_integral(G_derivation,G);
		}
		friend void poly_exp(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			const int len=F.deg(),n=get_n(len);
			F.v.resize(n<<1);
			G.v.clear();
			G.v.emplace_back(1);
			Poly<T_store,T_calc>A,B,C;
			for(int l=1;l<=(len<<1);l<<=1){
				const int lim=l<<1;
				A.v.assign(F.v.begin(),F.v.begin()+l);
				B.v.assign(G.v.begin(),G.v.begin()+l);
				poly_ln(B,C);
				C=A-C;
				qmod(C.v[0]+=1-P);
				G=poly_multiply_reference(B,C,[](const T_store x,const T_store y){
					return T_store((T_calc)x*y%P);
				});
				for(int i=l;i<lim;i++)G.v[i]=0;
			}
			F.set_deg(len);
			G.set_deg(len);
		}
};
Poly<int,ll>A,B,eB,eB_inv,F0,C0,Cn,Fn;
void solve(){
	A.clear(),B.clear(),eB.clear(),eB_inv.clear(),F0.clear(),C0.clear(),Cn.clear(),Fn.clear();
	int n,k;
	read(n),read(k);
	A.set_deg(n+k-1);
	for(int i=1;i<n;i++)read(A[i]);
	poly_integral(A,B);
	B=B*(P-1);
	poly_exp(B,eB);
	poly_inverse(eB,eB_inv);
	F0.set_deg(n-1);
	F0[n-1]=1;
	C0=F0*eB_inv;
	Cn.set_deg(n-1);
	for(int i=0;i<n;i++)Cn[i]=(ll)C0[i+k]*fac[i+k]%P*fac_inv[i]%P;
	eB.set_deg(n-1);
	Fn=Cn*eB;
	for(int i=n-1;i>=0;i--)write(Fn[i]),pc(i?' ':'\n');
}
int main(){
	int T;
	read(T);
	for(int i=1;i<=T;i++)solve();
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 5068ms
memory: 77304kb

input:

14
3 2
1 2

3 1
1 2

7 10
1 1 4 5 1 4

2 1
998244352

18 32
1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1

188 19
633886818 153877981 415015507 40745200 269787796 274990221 297547338 934403707 463583160 490465672 641355195 897012511 641637182 821068661 614724038 55504516 717220803 796828809 578138752 516258420 ...

output:

5 0 2
0 2 0
475251424 113315999 791330691 478266847 175921200 46569600 4082400
0 1
290297689 111948457 905336170 325091865 481715174 560516169 711953201 909617930 834449213 230629315 299970170 870572449 496138561 512305244 580683156 556935218 282162750 458443581
900977301 704879246 103685386 1134176...

result:

ok 14 lines
English 繁體中文 简体中文

服务器时间: 2024-11-30 09:47:49 | 开源项目