fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cctype>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<cmath>
  7. #include<cassert>
  8. #include<iostream>
  9. #define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
  10. #define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
  11. #define rep(i,a,b) for(register int i=(a);i<(b);++i)
  12. #define pb push_back
  13. #define mx(a,b) (a>b?a:b)
  14. #define mn(a,b) (a<b?a:b)
  15. typedef unsigned long long uint64;
  16. typedef unsigned int uint32;
  17. typedef long long ll;
  18. using namespace std;
  19.  
  20. namespace IO
  21. {
  22. 	const uint32 Buffsize=1<<15,Output=1<<24;
  23. 	static char Ch[Buffsize],*S=Ch,*T=Ch;
  24. 	inline char getc()
  25. 	{
  26. 		return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
  27. 	}
  28. 	static char Out[Output],*nowps=Out;
  29.  
  30. 	inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
  31.  
  32. 	template<typename T>inline void read(T&x)
  33. 	{
  34. 		x=0;static char ch;T f=1;
  35. 		for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
  36. 		for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
  37. 		x*=f;
  38. 	}
  39.  
  40. 	template<typename T>inline void write(T x,char ch='\n')
  41. 	{
  42. 		if(!x)*nowps++='0';
  43. 		if(x<0)*nowps++='-',x=-x;
  44. 		static uint32 sta[111],tp;
  45. 		for(tp=0;x;x/=10)sta[++tp]=x%10;
  46. 		for(;tp;*nowps++=sta[tp--]^48);
  47. 		*nowps++=ch;
  48. 	}
  49. }
  50. using namespace IO;
  51.  
  52. void file()
  53. {
  54. #ifndef ONLINE_JUDGE
  55. 	FILE*DSD=freopen("water.in","r",stdin);
  56. 	FILE*CSC=freopen("water.out","w",stdout);
  57. #endif
  58. }
  59.  
  60. const int MAXN=1<<17;
  61.  
  62. static int mod;
  63.  
  64. namespace poly
  65. {
  66. 	inline int power(int u,int v)
  67. 	{
  68. 		register int sm=1;
  69. 		for(;v;v>>=1,u=(uint64)u*u%mod)if(v&1)
  70. 			sm=(uint64)sm*u%mod;
  71. 		return sm;
  72. 	}
  73.  
  74. 	static int Len,rev[MAXN];
  75.  
  76. 	static struct comp
  77. 	{
  78. 		double re,im;
  79.  
  80. 		comp(){}
  81.  
  82. 		comp(double _r,double _i):re(_r),im(_i){}
  83.  
  84. 		comp operator+(const comp&a){return comp(re+a.re,im+a.im);}
  85.  
  86. 		comp operator-(const comp&a){return comp(re-a.re,im-a.im);}
  87.  
  88. 		comp operator*(const comp&a)
  89. 		{return comp(re*a.re-im*a.im,re*a.im+im*a.re);}
  90.  
  91. 		comp operator/(const int&a){return comp(re/a,im/a);}
  92. 	}g[19][MAXN];
  93.  
  94. 	namespace MTT
  95. 	{
  96. 		const double pi=acos(-1);
  97.  
  98. 		inline void predone()
  99. 		{
  100. 			Rep(i,1,17)rep(j,0,1<<i)
  101. 				g[i][j]=comp(cos(2*pi*j/pow(2,i)),sin(2*pi*j/pow(2,i)));
  102. 		}
  103.  
  104. 		inline void FFT(comp*F,int tl)
  105. 		{
  106. 			rep(i,0,Len)if(i<rev[i])swap(F[rev[i]],F[i]);
  107. 			for(register int i=2,ii=1,t=1;i<=Len;i<<=1,ii<<=1,++t)
  108. 				for(register int j=0;j<Len;j+=i)rep(k,0,ii)
  109. 				{
  110. 					comp x=F[j+k+ii]*g[t][k];
  111. 					F[j+k+ii]=F[j+k]-x;
  112. 					F[j+k]=F[j+k]+x;
  113. 				}
  114. 			if(tl==-1)
  115. 			{
  116. 				reverse(F+1,F+Len);
  117. 				rep(i,0,Len)F[i]=F[i]/Len;
  118. 			}
  119. 		}
  120.  
  121. 		static comp Z[MAXN];
  122.  
  123. 		inline void DBLFFT(comp*F,comp*G,int tl)
  124. 		{
  125. 			if(tl==1)
  126. 			{
  127. 				memcpy(Z,F,sizeof(comp)*Len);
  128. 				FFT(Z,1);
  129. 				memcpy(F,Z,sizeof(comp)*Len);
  130. 				reverse(F+1,F+Len);
  131. 				rep(i,0,Len)F[i].im=-F[i].im;
  132. 				rep(i,0,Len)G[i]=(Z[i]-F[i])/2,F[i]=(Z[i]+F[i])/2
  133. 					,swap(G[i].re,G[i].im),G[i].im=-G[i].im;
  134. 			}
  135. 			else
  136. 			{
  137. 				rep(i,0,Len)F[i]=comp(F[i].re-G[i].im,F[i].im+G[i].re);
  138. 				FFT(F,-1);
  139. 				rep(i,0,Len)G[i]=comp(F[i].im,0),F[i]=comp(F[i].re,0);
  140. 			}
  141. 		}
  142. 	}
  143. 	using MTT::predone;
  144. 	using MTT::DBLFFT;
  145. 	using MTT::FFT;
  146.  
  147. 	inline void calrev()
  148. 	{
  149. 		int II=log(Len)/log(2)-1;
  150. 		Rep(i,1,Len-1)rev[i]=rev[i>>1]>>1|(i&1)<<II;
  151. 	}
  152.  
  153. 	inline int ad(int u,int v)
  154. 	{return ((unsigned)u+v>=mod?(unsigned)u+v-mod:u+v);}
  155.  
  156. 	static int X[MAXN],Y[MAXN],Iv[MAXN],mlx[MAXN];
  157.  
  158. 	static comp A[MAXN],B[MAXN],C[MAXN],D[MAXN];
  159.  
  160. 	inline void mul(int*F,int*G,int*H,int lenl,int lenr)
  161. 	{
  162. 		if((ll)lenl*lenr<=300)
  163. 		{
  164. 			Rep(i,0,lenl+lenr)mlx[i]=0;
  165. 			Rep(i,0,lenl)Rep(j,0,lenr)
  166. 				mlx[i+j]=(mlx[i+j]+(ll)F[i]*G[j])%mod;
  167. 			Rep(i,0,lenl+lenr)H[i]=mlx[i];
  168. 			return;
  169. 		}
  170. 		for(Len=2;Len<=lenl+lenr;Len<<=1);
  171. 		calrev();
  172. 		rep(i,0,Len)A[i]=i<=lenl?comp(F[i]>>15,F[i]&32767):comp(0,0),
  173. 			C[i]=i<=lenr?comp(G[i]>>15,G[i]&32767):comp(0,0);
  174. 		DBLFFT(A,B,1),DBLFFT(C,D,1);
  175. 		rep(i,0,Len)
  176. 		{
  177. 			register comp t=A[i];
  178. 			A[i]=B[i]*C[i]+A[i]*D[i];
  179. 			B[i]=B[i]*D[i];
  180. 			C[i]=C[i]*t;
  181. 		}
  182. 		DBLFFT(A,B,-1),FFT(C,-1);
  183. 		rep(i,0,Len)
  184. 		{
  185. 			register int lz=((((ll)floor(C[i].re+0.5))%mod<<30)%mod
  186. 				 +((ll)floor(A[i].re+0.5))%mod*32768+(ll)floor(B[i].re+0.5))%mod;
  187. 			H[i]=i<=lenl+lenr?lz:0;
  188. 		}
  189. 	}
  190.  
  191. 	inline void Inv(int*F,int*G,int ln)
  192. 	{
  193. 		Iv[0]=power(F[0],mod-2);
  194. 		for(register int Ln=2;Ln>>1<=ln;Ln<<=1)
  195. 		{
  196. 			rep(i,ln+1,Ln)F[i]=0;
  197. 			rep(i,0,Ln)X[i]=F[i],Y[i]=0;
  198. 			rep(i,0,(Ln>>1))Y[i]=Iv[i];
  199. 			mul(Y,X,X,(Ln>>1)-1,Ln-1),--X[0];
  200. 			mul(X,Y,X,Ln-1,(Ln>>1)-1);
  201. 			rep(i,(Ln>>1),Ln)Iv[i]=mod-X[i];
  202. 		}
  203. 		Rep(i,0,ln)G[i]=Iv[i];
  204. 	}
  205.  
  206. 	static int ExX[MAXN],ExY[MAXN];
  207.  
  208. 	inline void Div(int*F,int*G,int*Q,int*R,int lenf,int leng)
  209. 	{
  210. 		Rep(i,0,lenf)ExX[i]=F[lenf-i];
  211. 		Rep(i,0,leng)ExY[i]=G[leng-i];
  212. 		Rep(i,leng+1,lenf-leng)ExY[i]=0;
  213. 		Inv(ExY,ExY,lenf-leng);
  214. 		Rep(i,lenf-leng+1,lenf)ExX[i]=0;
  215. 		Rep(i,lenf-leng+1,leng)ExY[i]=0;
  216. 		mul(ExX,ExY,ExY,lenf-leng,lenf-leng);
  217. 		Rep(i,lenf-leng+1,(lenf-leng)<<1)ExY[i]=0;
  218. 		Rep(i,0,(lenf-leng)>>1)swap(ExY[i],ExY[lenf-leng-i]);
  219. 		mul(ExY,G,ExX,lenf-leng,leng);
  220. 		Rep(i,0,leng-1)R[i]=ad(F[i],mod-ExX[i]);
  221. 		Rep(i,0,lenf-leng)Q[i]=ExY[i];
  222. 	}
  223.  
  224. 	namespace Extend
  225. 	{
  226. 		static int solv[18][2][MAXN];
  227.  
  228. 		void calc(int*a,int l,int r,int lev,int dir)
  229. 		{
  230. 			if(l==r)
  231. 			{
  232. 				solv[lev][dir][0]=mod-a[l];
  233. 				solv[lev][dir][1]=1;return;
  234. 			}
  235. 			int md=(l+r)>>1;
  236. 			calc(a,l,md,lev+1,0),calc(a,md+1,r,lev+1,1);
  237. 			mul(solv[lev+1][0],solv[lev+1][1],solv[lev][dir],md-l+1,r-md);
  238. 		}
  239.  
  240. 		static int pol[18][MAXN],Q[MAXN];
  241.  
  242. 		void getnum(int*a,int*ans,int l,int r,int lev,int n)
  243. 		{
  244. 			if(n>r-l)
  245. 			{
  246. 				calc(a,l,r,0,0);
  247. 				Div(pol[lev-(lev>0)],solv[0][0],Q,pol[lev],n,r-l+1);
  248. 				n=r-l;
  249. 			}
  250. 			else if(lev){Rep(i,0,n)pol[lev][i]=pol[lev-1][i];}
  251. 			if(l==r)
  252. 			{
  253. 				ans[l]=pol[lev][0];
  254. 				return;
  255. 			}
  256. 			int md=(l+r)>>1;
  257. 			getnum(a,ans,l,md,lev+1,n);
  258. 			getnum(a,ans,md+1,r,lev+1,n);
  259. 		}
  260. 	}
  261. }
  262. using poly::power;
  263. using poly::predone;
  264. using poly::ad;
  265. using poly::Extend::pol;
  266. using poly::Extend::getnum;
  267. using poly::Extend::calc;
  268. using poly::Extend::solv;
  269.  
  270. static int n,Z[MAXN],as[MAXN];
  271.  
  272. void solve()
  273. {
  274. 	read(n),read(mod);
  275. 	int v=sqrt(n);
  276. 	Rep(i,1,v)Z[i]=mod-i;
  277. 	calc(Z,1,v,0,0);
  278. 	memcpy(pol[0],solv[0][0],sizeof(int)*(v+1));
  279. 	Rep(i,1,v)Z[i]=(i-1)*v;
  280. 	getnum(Z,as,1,v,0,v);
  281. 	static int ans=1;
  282. 	Rep(i,1,v)ans=(ll)ans*as[i]%mod;
  283. 	Rep(i,v*v+1,n)ans=(ll)ans*i%mod;
  284. 	cout<<ans<<endl;
  285. }
  286. int main()
  287. {
  288.     int T;read(T);
  289.     while(T--)solve();
  290. }
Success #stdin #stdout 4.77s 35672KB
comments (?)
stdin
copy 
3
1073741823 2147483629
1073741823 2147481811
2147483628 2147483629
stdout
copy 
897275997
1969615855
1870532358
https://ideone.com/H6uB46
hack for FACTMODP
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!