Advertisement
daskalot

Untitled

Apr 23rd, 2019
237
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.47 KB | None | 0 0
  1. import java.util.Scanner;
  2. class Complex{
  3. double re; double im;
  4. public Complex(double real, double imag) {
  5. re = real;
  6. im = imag;
  7. }
  8. public String toString() {
  9. double tRe = (double)Math.round(re * 100000) / 100000;
  10. double tIm = (double)Math.round(im * 100000) / 100000;
  11. if (tIm == 0) return tRe + "";
  12. if (tRe == 0) return tIm + "i";
  13. if (tIm < 0) return tRe + "-" + (-tIm) + "i";
  14. return tRe + "+" + tIm + "i";
  15. }
  16. public Complex conj() {
  17. return new Complex(re, -im);
  18. }
  19. public Complex plus(Complex b) {
  20. Complex a = this;
  21. double real = a.re + b.re;
  22. double imag = a.im + b.im;
  23. return new Complex(real, imag);
  24. }
  25. public Complex minus(Complex b) {
  26. Complex a = this;
  27. double real = a.re - b.re;
  28. double imag = a.im - b.im;
  29. return new Complex(real, imag);
  30. }
  31. public Complex times(Complex b) {
  32. Complex a = this;
  33. double real = a.re * b.re - a.im * b.im;
  34. double imag = a.re * b.im + a.im * b.re;
  35. return new Complex(real, imag);
  36. }
  37. public Complex times(double alpha) {
  38. return new Complex(alpha * re, alpha * im);
  39. }
  40. public Complex reciprocal() {
  41. double scale = re*re + im*im;
  42. return new Complex(re / scale, -im / scale);
  43. }
  44. public Complex divides(Complex b) {
  45. Complex a = this;
  46. return a.times(b.reciprocal());
  47. }
  48. public Complex exp() {
  49. return new Complex(Math.exp(re) * Math.cos(im), Math.exp(re) * Math.sin(im));
  50. }
  51. public Complex pow(int k) {
  52. Complex c = new Complex(1,0);
  53. for (int i = 0; i <k ; i++) {
  54. c = c.times(this);
  55. }
  56. return c;
  57. }
  58. }
  59. public class Izziv8{
  60. public static int N;
  61. public static Complex coeffA[];
  62. public static Complex coeffB[];
  63. public static void read(){
  64. Scanner sc = new Scanner(System.in);
  65. N = sc.nextInt();
  66. coeffA = new Complex[2*N]; coeffB = new Complex[2*N];
  67. for(int i=0;i<N;i++) coeffA[i]=new Complex(sc.nextDouble(),0);
  68. for(int i=0;i<N;i++) coeffB[i]=new Complex(sc.nextDouble(),0);
  69. for(int i=N;i<2*N;i++) coeffA[i]=coeffB[i]=new Complex(0,0);
  70. sc.close();
  71. }
  72. public static void solve(){
  73. Complex[] p = FFT(coeffA);
  74. Complex[] s = FFT(coeffB);
  75. Complex[] c = new Complex[2*N];
  76. for(int i=0;i<2*N;i++) c[i] = p[i].times(s[i]);
  77. Complex[] y = iFFT2(c);
  78. Complex _n = new Complex(2*N,0);
  79. for(int i=0;i<2*N;i++) y[i] = y[i].divides(_n);
  80. for(int i=0;i<2*N;i++) System.out.printf("%s ",y[i].toString());
  81. }
  82. public static Complex[] FFT(Complex[] a){
  83. int n = a.length;
  84. if(n == 1) return a;
  85. Complex[] pEven = new Complex[n/2];
  86. for(int i=0;i<n/2;i++) pEven[i] = a[i*2];
  87. Complex[] ys = FFT(pEven);
  88. Complex[] pOdd = new Complex[n/2];
  89. for(int i=0;i<n/2;i++) pOdd[i] = a[i*2+1];
  90. Complex[] yl = FFT(pOdd);
  91. Complex w = new Complex(Math.cos(2*Math.PI/n), Math.sin(2*Math.PI/n));
  92. Complex wk = new Complex(1,0);
  93. Complex[] y = new Complex[n];
  94. for(int i=0;i<n/2;i++){
  95. y[i] = ys[i].plus(wk.times(yl[i]));
  96. y[i+n/2] = ys[i].minus(wk.times(yl[i]));
  97. wk = wk.times(w);
  98. }
  99. for(int i=0;i<n;i++) System.out.printf("%s ",y[i].toString());
  100. System.out.printf("\n");
  101. return y;
  102. }
  103. public static Complex[] iFFT2(Complex [] a){
  104. int n = a.length;
  105. if(n==1) return a;
  106. Complex[] pEven = new Complex[n/2];
  107. for(int i=0;i<n/2;i++) pEven[i] = a[i*2];
  108. Complex[] ys = FFT(pEven);
  109. Complex[] pOdd = new Complex[n/2];
  110. for(int i=0;i<n/2;i++) pOdd[i] = a[i*2+1];
  111. Complex[] yl = FFT(pOdd);
  112. Complex w = new Complex(Math.cos(2*Math.PI/n), Math.sin(2*Math.PI/n));
  113. w = w.reciprocal();
  114. Complex wk = new Complex(1,0);
  115. Complex[] y = new Complex[n];
  116. for(int i=0;i<n/2;i++){
  117. y[i] = ys[i].plus(wk.times(yl[i]));
  118. y[i+n/2] = ys[i].minus(wk.times(yl[i]));
  119. wk = wk.times(w);
  120. }
  121. for(int i=0;i<n;i++) System.out.printf("%s ",y[i].toString());
  122. System.out.printf("\n");
  123. return y;
  124. }
  125. public static void main(String[] args) {
  126. read();
  127. solve();
  128. }
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement