fork download
copy 
  1. /***************************************************************
  2. *             Author : Nguyen Trong Van Viet                   *
  3. *                        Age : 17                              *
  4. *      School : 12T2 Le Khiet High School for the Gifted       *
  5. *            Hometown :  Quang Ngai , Viet Nam .               *
  6. * Khanh An is my lover :) the more I code  , the nearer I am   *
  7. ****************************************************************/
  8. #define TASK "text"
  9. #define INPUT TASK".INP" 
  10. #define OUTPUT TASK".OUT"
  11.  
  12. bool mtt = 0 ;
  13. int test = 1 ;  
  14.  
  15. #include<bits/stdc++.h>
  16. using namespace std; 
  17.  
  18. #define             ll  long long 
  19. #define             db  double 
  20. #define             ve  vector 
  21. #define             vi  vector<int>
  22. #define            vll  vector<ll>
  23. #define            str  string
  24. #define             pb  push_back
  25. #define             pk  pop_back
  26. #define             el  '\n'
  27. #define            pii  pair<int,int>
  28. #define            pll  pair<ll,ll>
  29. #define             mp  make_pair 
  30. #define             fi  first 
  31. #define             se  second
  32. #define         uni(a)  sort(all(a)),a.resize(unique(all(a))-a.begin()) 
  33. #define     FOR(i,a,b)  for(int i=(int)(a);i<=(int)(b);i++)
  34. #define    FORD(i,a,b)  for(int i=(int)(a);i>=(int)(b);i--)
  35. #define    FORN(i,a,b)  for(int i=(int)(a);i<(int)(b);i++)
  36. #define         all(a)  a.begin(),a.end()  
  37. #define           btpc  __builtin_popcountll
  38. #define             LB  lower_bound
  39. #define             UB  upper_bound 
  40. #define            tct  template<class T>
  41. #define     BIT(msk,i)  (msk>>(i)&1)
  42.  
  43. ll lg(ll a){return __lg(a);}
  44. ll sq(ll a){return a*a;}  
  45. ll gcd(ll a,ll b){return __gcd(a,b);} 
  46. ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
  47. ll rd(ll l , ll r ){return l+1LL*rand()*rand()*rand()%(r-l+1);}
  48.  
  49. #define prt(a,n) FOR(i,1,n)cout<<a[i]<<" ";cout<<el;
  50. #define prv(a) for(auto v:a)cout<<v<<" "; cout<<el; 
  51.  
  52. tct bool mini(T& a,T b){return (a>b)?a=b,1:0;}
  53. tct bool maxi(T& a,T b){return (a<b)?a=b,1:0;}
  54.  
  55. int xx[] = {0,0,-1,0,1}; 
  56. int yy[] = {0,-1,0,1,0};
  57.  
  58. const db PI = acos(-1) , EPS = 1e-9;
  59. const ll inf = 1e18 , cs = 331 , sm = 1e9+7; 
  60. const int N = 2e5+5 , oo = 2e9 , LO = 17 , CH = 26 ; 
  61.  
  62. const ll mod = (119 << 23) + 1, root = 62; // = 998244353
  63. // For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
  64. // and 483 << 21 (same root). The last two are > 10^9.
  65. ll pw(ll a,ll b)
  66. {
  67. 	ll res = 1 ; 
  68. 	while(b)
  69. 	{
  70. 		if(b&1)res = res*a%mod ; 
  71. 		a = a*a%mod ; 
  72. 		b>>=1 ; 
  73. 	}
  74. 	return res ; 
  75. }
  76. void ntt(vll &a) 
  77. {
  78. 	int n = a.size(), L = 31 - __builtin_clz(n);
  79. 	static vll rt(2, 1);
  80. 	for (static int k = 2, s = 2; k < n; k *= 2, s++) {
  81. 		rt.resize(n);
  82. 		ll z[] = {1, pw(root, mod >> s)};
  83. 		FORN(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
  84. 	}
  85. 	vi rev(n);
  86. 	FORN(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
  87. 	FORN(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
  88. 	for (int k = 1; k < n; k *= 2)
  89. 		for (int i = 0; i < n; i += 2 * k) FORN(j,0,k) {
  90. 			ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
  91. 			a[i + j + k] = ai - z + (z > ai ? mod : 0);
  92. 			ai += (ai + z >= mod ? z - mod : z);
  93. 		}
  94. }
  95. vll conv(vll a, vll b) {
  96. 	if (a.empty() || b.empty()) return {};
  97. 	int s = (int)a.size() + (int)b.size() - 1, B = 32 - __builtin_clz(s),
  98. 		n = 1 << B;
  99. 	int inv = pw(n, mod - 2);
  100. 	vll L(a), R(b), out(n);
  101. 	L.resize(n), R.resize(n);
  102. 	ntt(L), ntt(R);
  103. 	FORN(i,0,n)
  104. 		out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
  105. 	ntt(out);
  106. 	return {out.begin(), out.begin() + s};
  107. }
  108. struct poly
  109. {
  110. 	vll coef; 
  111. 	poly(){} 
  112. 	poly(vll a) : coef(a){}  
  113. 	friend poly operator*(poly a,poly b){return conv(a.coef,b.coef);}
  114. 	friend poly operator+(int a , poly b )
  115. 	{
  116. 		b.coef[0] = (a+b.coef[0])%mod ;
  117. 		return b ;
  118. 	}
  119. 	friend poly operator-(int a , poly b )
  120. 	{
  121. 		for(auto &x:b.coef)x=(mod-x)%mod ; 
  122. 		return a+b ; 
  123. 	}
  124. 	friend poly operator+(poly a,poly b)
  125. 	{
  126. 		a.coef.resize(max(a.coef.size(),b.coef.size())) ; 
  127. 		FORN(i,0,b.coef.size())a.coef[i] = (a.coef[i]+b.coef[i])%mod ; 
  128. 		return a ; 
  129. 	}
  130. 	friend poly operator-(poly a,poly b)
  131. 	{
  132. 		for(auto &x : b.coef)x = (mod-x)%mod ;
  133. 		return a+b ; 
  134. 	}
  135. 	void mod_xk(int k)
  136. 	{
  137. 		coef.resize(min(k,(int)coef.size())) ; 
  138. 	}
  139. 	poly mod_xk_here(int k)
  140. 	{
  141. 		poly r = *this ; 
  142. 		r.mod_xk(k) ; 
  143. 		return r ; 
  144. 	}
  145. 	int deg()
  146. 	{
  147. 		return coef.size()-1 ; 
  148. 	}
  149. 	poly inv()
  150. 	{	
  151. 		assert(coef[0]!=0) ;
  152. 		poly r({pw(coef[0],mod-2)}) ; 
  153. 		for(int d=2;d<=deg()*2;d*=2)
  154. 		{
  155. 			poly f = poly({coef.begin(),coef.begin()+min((int)coef.size(),d)}) ; 
  156. 			poly g = r*f ; 
  157. 			g.mod_xk(d) ; 
  158. 			poly h = r*(2-g) ; 
  159. 			h.mod_xk(d) ; 
  160. 			r.coef.resize(d) ; 
  161. 			for(int i=0;i<d;i++)r.coef[i] = h.coef[i] ; 
  162. 		}
  163. 		r.coef.resize(deg()+1) ; 
  164. 		return r ; 
  165. 	}
  166. 	poly deri()
  167. 	{
  168. 		vll r ; 
  169. 		for(int i=1;i<=deg();i++)r.pb(coef[i]*i%mod) ; 
  170. 		return poly(r) ;
  171. 	}
  172. 	poly inte()
  173. 	{
  174. 		vll r = {0} ; 
  175. 		for(int i=0;i<=deg();i++)r.pb(coef[i]*pw(i+1,mod-2)%mod) ; 
  176. 		return poly(r) ; 
  177. 	}
  178. 	// ln(A(x))' = A'(x)/A(x) 
  179. 	poly ln(int k = -1 )
  180. 	{   
  181. 		assert(coef[0]==1) ; 
  182. 		if(k==-1)
  183. 		{
  184. 			k = deg()+1 ; 
  185. 		}
  186. 		return (deri()*inv()).mod_xk_here(k).inte().mod_xk_here(k) ; 
  187. 	}
  188. 	poly exp()
  189. 	{
  190. 		assert(coef[0]==0) ;   
  191. 		poly Q({1}) ;
  192. 		for(int d=2;d<=deg()*2;d*=2)
  193. 		{
  194. 			poly P = poly({coef.begin(),coef.begin()+min((int)coef.size(),d)}) ; 
  195. 			poly q = Q*(1+P-Q.ln()) ; 
  196. 			q.mod_xk(d) ; 
  197. 			Q.coef.resize(d) ; 
  198. 			for(int i=0;i<d;i++)Q.coef[i] = q.coef[i] ; 
  199. 		}	 
  200. 		Q.coef.resize(deg()+1) ;
  201. 		return Q ;
  202. 	}
  203. };
  204.  
  205. int n ; 
  206. void doc()
  207. {
  208. 	cin>> n  ;
  209. 	vll a(n) ; 
  210. 	for(int i=0;i<n;i++)cin>>a[i]  ; 
  211. 	poly b = poly(a) ;
  212. 	prv(b.exp().coef) ;  
  213.  
  214. }
  215. namespace sub1
  216. {
  217. 	void xuly()
  218. 	{	
  219.  
  220. 	}		
  221. }
  222.  
  223. /*  DON'T BELIEVE LOVE WILL INSPIRE YOU ->  TRAIN HARDER ->  YOU WILL GET THE LOVE YOU WANT !!*/
  224.  
  225. signed main()
  226. {
  227. 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
  228. 	if(fopen(INPUT,"r"))
  229. 	{
  230. 		freopen(INPUT ,"r",stdin);
  231. 		freopen(OUTPUT,"w",stdout);
  232. 	}
  233. 	if(mtt)cin>>test;
  234.  
  235. 	FOR(i,1,test)
  236. 	{
  237. 		doc() ; 
  238. 		sub1::xuly() ; 
  239. 	}
  240. }
Runtime error #stdin #stdout 0.04s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Kw9hqu
language:
C++14 (gcc 8.3)
created:
24 days 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!