fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define CP complex<double>
  4. #define VCP vector<complex<double> >
  5. vector <CP> universal; 
  6. const double PI=3.1415926535897932; 
  7. const int MAXN = (1<<15); 
  8. const double eps=1e-9; 
  9. double rounder (double x)
  10. {
  11. 	if (x-floor(x)<eps)
  12. 	{
  13. 		return floor(x); 
  14. 	}
  15. 	return x;
  16. }
  17. VCP fft (VCP coefficients, vector <CP> eval)
  18. {
  19. 	if (coefficients.size()==1)
  20. 	{
  21. 		VCP basecase; 
  22. 		basecase.push_back(coefficients[0]);
  23. 		return basecase; 
  24. 	}
  25. 	VCP coeff1, coeff2; 
  26. 	vector <CP> eval1, eval2;
  27. 	for (int g=0; g<coefficients.size(); g+=2) coeff1.push_back(coefficients[g]); 
  28. 	for (int g=1; g<coefficients.size(); g+=2) coeff2.push_back(coefficients[g]); 
  29. 	for (int g=0; g<eval.size()/2; g++) eval1.push_back(eval[g]*eval[g]);
  30. 	for (int g=eval.size()/2; g<eval.size(); g++) eval2.push_back(eval[g]*eval[g]);
  31. 	VCP first=fft(coeff1, eval1), second=fft(coeff2, eval2);
  32. 	VCP toreturn; 
  33. 	for (int g=0; g<coefficients.size(); g++)
  34. 	{
  35. 		if (g<coefficients.size()/2)
  36. 		{
  37. 			toreturn.push_back(first[g]+eval[g]*second[g]);
  38. 		}
  39. 		else
  40. 		{
  41. 			toreturn.push_back(first[g-coefficients.size()/2]+eval[g]*second[g-coefficients.size()/2]); 
  42. 		}
  43. 	}
  44. 	return toreturn; 
  45. } 
  46. vector <int> interpolate (VCP a, VCP b)
  47. {
  48. 	VCP first=fft(a,universal);
  49. 	VCP second=fft(b,universal); 
  50. 	VCP third;
  51. 	for (int g=0; g<first.size(); g++) third.push_back(first[g]*second[g]);
  52. 	for (int g=0; g<universal.size(); g++) universal[g]=complex<double>(1,0)/universal[g]; 
  53. 	//cout << second[0] << '\n';
  54. 	VCP fincoff=fft(third, universal); 
  55. 	for (int g=0; g<universal.size(); g++) universal[g]=complex<double>(1,0)/universal[g]; 
  56. 	//for (int g=0; g<fincoff.size(); g++) cout << fincoff[g] << '\n'; cout<<'\n';
  57. 	vector <int> answer;
  58. 	for (int g=0; g<fincoff.size(); g++)
  59. 	{
  60. 		answer.push_back(real(fincoff[g]+0.5)/MAXN); 
  61. 	}	
  62. 	return answer; 
  63. }
  64. void fill (VCP & a)
  65. {
  66. 	int m=a.size(); 
  67. 	for (int g=0; g<MAXN-m; g++) a.push_back(complex<double>(0,0));
  68. }
  69. int main()
  70. {
  71. 	ios_base::sync_with_stdio(0); 
  72. 	int T; cin >> T;
  73. 	for (int g=0; g<T; g++)
  74. 	{
  75. 		universal.clear(); 
  76. 		for (int g=0; g<MAXN; g++)
  77. 		{
  78. 		universal.push_back(complex <double> (rounder(cos((double)g*(2*PI)/(double) MAXN)), rounder(sin((double)g*(2*PI)/(double) MAXN))));
  79. 		}
  80. 		VCP a, b; 
  81. 		int N; cin >> N; 
  82. 		for (int g=0; g<N+1; g++)
  83. 		{
  84. 			int t; cin >> t; a.push_back(complex<double> (t, 0)); 
  85. 		}
  86. 		for (int g=0; g<N+1; g++)
  87. 		{
  88. 			int t; cin >> t; b.push_back(complex<double> (t, 0)); 
  89. 		}
  90. 		reverse(a.begin(), a.end()); 
  91. 		reverse(b.begin(), b.end()); 
  92. 		fill (a); 
  93. 		fill(b);
  94. 		vector <int> ans=interpolate(a, b); 
  95. 		reverse(ans.begin(), ans.begin()+2*N+1);
  96. 		for (int g=0; g<2*N+1; g++) cout << ans[g] << ' '; 
  97. 		cout << '\n';
  98. 	}
  99. 	return 0; 
  100. }
Success #stdin #stdout 0.71s 3352KB
comments (?)
stdin
copy 
2
2
1 2 3
3 2 1
2
1 0 1
2 1 0
stdout
copy 
3 8 14 8 3 
2 1 2 1 0
https://ideone.com/wuD2H4
language:
C++14 (gcc 8.3)
created:
9 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!