fork download
copy 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890123456789LL
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. typedef long long cat;
  35.  
  36. #ifdef DONLINE_JUDGE
  37. 	// palindromic tree is better than splay tree!
  38. 	#define lld I64d
  39. #endif
  40.  
  41. inline cat pw(cat a, cat e, cat mod) {
  42. 	cat x =a, ret =1;
  43. 	while(e > 0) {
  44. 		if(e&1) ret =(ret*x)%mod;
  45. 		x =(x*x)%mod;
  46. 		e /=2;
  47. 	}
  48. 	return ret;
  49. }
  50.  
  51. cat mod =330301441;
  52.  
  53. cat w[11] ={0,0,330301440,93236247,39710288,161934030,93236248,7691605,90917647,25847905,7743336};
  54.  
  55. int main() {
  56. 	cin.sync_with_stdio(0);
  57. 	cin.tie(0);
  58. 	cout << fixed << setprecision(10);
  59. 	int T;
  60. 	cin >> T;
  61. 	vector<cat> pw2(200000,1);
  62. 	for(int i =1; i < 200000; i++) pw2[i] =(pw2[i-1]*2)%mod;
  63. 	while(T--) {
  64. 		int N,K;
  65. 		cat X;
  66. 		cin >> N >> K >> X;
  67. 		vector<int> A(N);
  68. 		for(int i =0; i < N; i++) {
  69. 			cin >> A[i];
  70. 			A[i] =min(N+1,A[i]);
  71. 		}
  72.  
  73. 		// compute P1
  74. 		vector<int> s(N+2,0);
  75. 		for(int i =0; i < N; i++) s[A[i]]++;
  76. 		int max_mex =0;
  77. 		while(s[max_mex]) max_mex++;
  78. 		vector<cat> prefprod(N+3,1), sufprod(N+3,1);
  79. 		for(int i =1; i <= N+1; i++) prefprod[i] =prefprod[i-1]*(pw(2,s[i-1],mod)-1)%mod;
  80. 		for(int i =N+1; i >= 0; i--) sufprod[i] =sufprod[i+1]*pw(2,s[i],mod)%mod;
  81. 		vector<cat> P1(max_mex+1);
  82. 		for(int i =0; i <= max_mex; i++) P1[i] =prefprod[i]*sufprod[i+1]%mod;
  83. 		// normalize
  84. 		cat sum =0;
  85. 		for(int i =0; i <= max_mex; i++) sum +=P1[i];
  86. 		sum =pw(sum%mod,mod-2,mod);
  87. 		for(int i =0; i <= max_mex; i++) P1[i] =(sum*P1[i])%mod;
  88.  
  89. 		// multidimensional NTT
  90. 		int D =0, Pw =1;
  91. 		while(max_mex+1 >= Pw) Pw *=K, D++;
  92. 		vector<cat> pwK(D+1,1);
  93. 		for(int i =1; i <= D; i++) pwK[i] =(pwK[i-1]*K)%mod;
  94. 		vector< vector<cat> > pwW(K,vector<cat>(K,1)); // powers of primitive root
  95. 		for(int i =0; i < K; i++) for(int j =0; j < K; j++)
  96. 			for(int k =0; k < (i*j); k++) pwW[i][j] =(pwW[i][j]*w[K])%mod;
  97. 		vector< vector<cat> > pwWI(K,vector<cat>(K,1)); // powers of inverse primitive root
  98. 		cat wi =pw(w[K],mod-2,mod);
  99. 		for(int i =0; i < K; i++) for(int j =0; j < K; j++)
  100. 			for(int k =0; k < (i*j); k++) pwWI[i][j] =(pwWI[i][j]*wi)%mod;
  101. 		P1.resize(Pw,0);
  102.  
  103. 		vector<cat> FP1 =P1;
  104. 		vector<cat> FP1_nxt(Pw,0); // after NTT-ing dimension d
  105. 		for(int d =0; d < D; d++) {
  106. 			for(int i =0; i < Pw; i++) {
  107. 				int d0 =(i/pwK[d])%K;
  108. 				int x =i-d0*pwK[d];
  109. 				FP1_nxt[i] =0;
  110. 				for(int j =0; j < K; j++)
  111. 					FP1_nxt[i] +=FP1[x+j*pwK[d]]*pwW[d0][j];
  112. 			}
  113. 			for(int i =0; i < Pw; i++) FP1[i] =FP1_nxt[i]%mod;
  114. 		}
  115.  
  116. 		// F[PX]
  117. 		vector<cat> FPX =FP1;
  118. 		X %=mod-1;
  119. 		for(int i =0; i < Pw; i++) FPX[i] =pw(FP1[i],X,mod);
  120.  
  121. 		// inverse transform
  122. 		vector<cat> PX =FPX;
  123. 		vector<cat> PX_nxt(Pw,0); // after NTT-ing dimension d
  124. 		for(int d =0; d < D; d++) {
  125. 			for(int i =0; i < Pw; i++) {
  126. 				int d0 =(i/pwK[d])%K;
  127. 				int x =i-d0*pwK[d];
  128. 				PX_nxt[i] =0;
  129. 				for(int j =0; j < K; j++)
  130. 					PX_nxt[i] +=PX[x+j*pwK[d]]*pwWI[d0][j];
  131. 			}
  132. 			for(int i =0; i < Pw; i++) PX[i] =PX_nxt[i]%mod;
  133. 		}
  134.  
  135. 		// compute the output hash
  136. 		cat ans =0, inv =pw(Pw,mod-2,mod);
  137. 		for(int i =0; i < Pw; i++) {
  138. 			if(PX[i] == 0 && i > 0) continue;
  139. 			PX[i] =(PX[i]*inv)%mod; // NTT wasn't normalised correctly
  140. 			cat q =1LL*i*i%mod*PX[i]%mod*PX[i]%mod*PX[i]%mod;
  141. 			ans +=pw(q,i,mod);
  142. 		}
  143. 		ans %=mod;
  144. 		if(ans < 0) ans +=mod;
  145. 		cout << ans << "\n";
  146. 	}
  147. }
  148.  
  149. // look at my code
  150. // my code is amazing
  151.  
Runtime error #stdin #stdout #stderr 0s 17632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/pksASp
Codechef October Challenge 2017, XORTREEH
language:
C++14 (gcc 8.3)
created:
6 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!