fork download
copy 
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. /* CF handle: haleyk100198*/
  4. #include <bits/stdc++.h>
  5.  
  6. #define MOD 998244353
  7. #define LINF (1LL<<60)
  8. #define INF 2147483647
  9. #define PI 3.1415926535897932384626433
  10. #define ll long long
  11. #define pii pair<int,int>
  12. #define mp(x,y) make_pair((x),(y))
  13. #define MAXN 16
  14. #define logMAXN 4
  15.  
  16. using namespace std;
  17.  
  18. string itos(int x){
  19. 	stringstream ss;
  20. 	ss << x;
  21. 	return ss.str();
  22. }
  23.  
  24. complex<double> dp[5][MAXN];
  25.  
  26. int rev[MAXN];
  27.  
  28. complex<double> lookup[MAXN]; 
  29.  
  30. int n, k;
  31.  
  32. void fft(complex<double> *a, int inv){
  33. 	for(int i = 0; i < MAXN; i++){
  34. 		if(rev[i] != -1)
  35. 			swap(a[rev[i]], a[i]);
  36. 	}
  37. 	complex<double> now; 
  38. 	for(int sz = 2; sz <= MAXN; sz <<= 1){
  39. 		int k = MAXN/sz;
  40. 		for(int i = 0; i < MAXN; i += sz){
  41. 			for(int j = 0; j < sz/2; j++){
  42. 				now = lookup[j*k];
  43. 				if(sz == MAXN && inv)
  44. 					now = conj(now);
  45. 				complex<double> x = a[i+j];
  46. 				complex<double> y = now*a[i+j+sz/2];
  47. 				a[i+j] = x+y;
  48. 				a[i+j+sz/2] = x-y;
  49. 			}
  50. 		}
  51. 	}
  52. 	if(inv)
  53. 		for(int i = 0; i < MAXN; i++)
  54. 			a[i] /= MAXN;
  55. }
  56.  
  57. int main(){
  58. 	//freopen("input.txt","r",stdin);
  59. 	//freopen("output.txt","w",stdout);
  60. 	ios_base::sync_with_stdio(false);
  61. 	cin >> n >> k;
  62. 	for(int i = 0; i < MAXN; i++){
  63. 		int t = i;
  64. 		int j = 0;
  65. 		for(int k = 0; k < logMAXN; k++){
  66. 			j <<= 1;
  67. 			j |= (i%2);
  68. 			i >>= 1;
  69. 		}
  70. 		i = t;
  71. 		if(i < j)
  72. 			rev[i] = j;
  73. 		else
  74. 			rev[i] = -1;
  75. 	}
  76. 	{
  77. 		complex<double> now = complex<double>(1, 0);
  78. 		complex<double> it = complex<double>(cos(2*PI/MAXN), sin(2*PI/MAXN));
  79. 		for(int j = 0; j < MAXN; j++){
  80. 			lookup[j] = now;
  81. 			now *= it;
  82. 		}
  83. 	}
  84. 	dp[1][0] = dp[0][1] = 1;
  85. 	dp[0][0] = 3;
  86. 	fft(dp[0], 0);
  87. 	for(int i = 0; i < MAXN; i++)
  88. 		cout << dp[0][i] << (i+1 == MAXN? '\n': ' ');
  89. 	/*for(int now = 2, dx = sizeof(int)*8 - __builtin_clz(n) - 2; now < n; dx--){
  90. 		if((n >> dx) % 2){
  91. 			for(int i = 0; i < MAXN; i++)
  92. 				dp[2][i] = dp[1][i], dp[1][i] = dp[0][i];
  93. 			for(int i = 0; i < MAXN; i++)
  94. 				dp[0][i] = dp[1][i] + (i? dp[1][i-1] + dp[2][i-1]: 2);
  95. 			now ^= 1;
  96. 		}
  97. 		if((now << 1) <= n){
  98. 			now <<= 1;
  99. 			for(int i = 0; i < 3; i++)
  100. 				fft(dp[i], 0);
  101. 			for(int j = 4; j >= 0; j--)
  102. 				for(int i = 0; i < MAXN; i++)
  103. 					dp[j][i] = dp[j/2][i] * dp[(j+1)/2][i];
  104. 			for(int i = 0; i < 5; i++){
  105. 				fft(dp[i], 1);
  106. 				for(int j = 0; j < MAXN; j++){
  107. 					dp[i][j].imag(0);
  108. 					dp[i][j].real(lround(fmod(dp[i][j].real(), MOD)));
  109. 				}
  110. 			}
  111. 			for(int i = 0; i < 5; i++){
  112. 				for(int k = 1; k < MAXN; k++){
  113. 					dp[i][k].real(fmod(dp[i+2][k-1].real()*dp[i+2][k-1].real()+dp[i][k].real(), MOD));
  114. 				}
  115. 			}
  116. 		}
  117. 	}
  118. 	if(n < 2)
  119. 		for(int i = 0; i < k; i++)
  120. 			cout << dp[2-n][i].real() << (i == k? '\n': ' ');
  121. 	else
  122. 		for(int i = 0; i < k; i++)
  123. 			cout << dp[0][i].real() << (i == k? '\n': ' ');*/
  124. 	return 0;
  125. }
  126.  
  127. /*
  128. Correct FFT output of dp[0] with a size 8 from online calculators
  129. in a form (real, imag)
  130. 4.000000,0.000000
  131. 3.923880,-0.382683
  132. 3.707107,-0.707107
  133. 3.382683,-0.923880
  134. 3.000000,-1.000000
  135. 2.617317,-0.923880
  136. 2.292893,-0.707107
  137. 2.076120,-0.382683
  138. 2.000000,0.000000
  139. 2.076120,0.382683
  140. 2.292893,0.707107
  141. 2.617317,0.923880
  142. 3.000000,1.000000
  143. 3.382683,0.923880
  144. 3.707107,0.707107
  145. 3.923880,0.382683
  146. */
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
4 1
stdout
copy 
(4,0) (3.92388,0.382683) (3.70711,0.707107) (3.38268,0.92388) (3,1) (2.61732,0.92388) (2.29289,0.707107) (2.07612,0.382683) (2,0) (2.07612,-0.382683) (2.29289,-0.707107) (2.61732,-0.92388) (3,-1) (3.38268,-0.92388) (3.70711,-0.707107) (3.92388,-0.382683)
https://ideone.com/tUoCwO
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!