package com.fftarry;
import java.io.*;
import java.util.*;
public class FFT {
public static ArrayList<ArrayList<Integer>> a,b;
public static int all;
public static ArrayList<ArrayList<Integer>> FFT(
ArrayList<ArrayList<Integer>> array, int step, int begin, int total){
if(total == 1){
ArrayList<ArrayList<Integer>> oddarray = new ArrayList<ArrayList<Integer>>();
oddarray.add(array.get(begin));
return oddarray;
}
else{
ArrayList<ArrayList<Integer>> u = FFT(array, step*2, begin, total/2);
ArrayList<ArrayList<Integer>> w = FFT(array, step*2, begin+Math.abs(step), total/2);
ArrayList<ArrayList<Integer>> newarray = new ArrayList<ArrayList<Integer>>();
for(int j=0; j<total; j++) newarray.add(new ArrayList<Integer>());
for(int j=0; j<total/2; j++){
ArrayList<Integer> result1 = new ArrayList<Integer>();
ArrayList<Integer> result2 = new ArrayList<Integer>();
for(int i=0; i<all/2; i++){
result1.add(u.get(j).get(i) + Handle(w.get(j), step*j).get(i));
result2.add(u.get(j).get(i) - Handle(w.get(j), step*j).get(i));
}
newarray.set(j, result1);
newarray.set(j+total/2, result2);
}
return newarray;
}
}
public static ArrayList<Integer> Mul(ArrayList<Integer> array1,ArrayList<Integer> array2){
int size = array1.size();
ArrayList<Integer> mularray = new ArrayList<Integer>();
for(int i = 0;i < size;i++) {
mularray.add(0);
}
for(int i = 0;i < size;i++){
mularray.add(0);
for(int j = 0;j < size;j++) mularray.set(j,
mularray.get(j)+Handle(array2,i).get(j)*array1.get(i));
}
return mularray;
}
public static ArrayList<Integer> Handle(ArrayList<Integer> h,int step){
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int i=0; i<all/2; i++) temp.add(0);
for(int i=0; i<all/2; i++){
if(i+step >= 0){
if(i+step < all/2) temp.set(i+step, h.get(i));
else {
if(i+step < all) temp.set(i+step-all/2, -h.get(i));
else temp.set(i+step-all, h.get(i));
}
}
else{
if(i+step >= -all/2) temp.set(i+step+all/2, -h.get(i));
else{
if(i+step >= -all) temp.set(i+step+all, h.get(i));
else temp.set(i+step+3*all/2, -h.get(i));
}
}
}
return temp;
}
//递归
public static void main(String arg[]) throws FileNotFoundException{
Input();
PrintWriter out = new PrintWriter(new File("result5.dat"));
ArrayList<ArrayList<Integer>> p = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> q = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> finalresult = new ArrayList<ArrayList<Integer>>();
p = FFT(a,1,0,all);
q = FFT(b,1,0,all);
for(int i = 0;i < p.size();i++) result.add(Mul(p.get(i),q.get(i)));
finalresult = FFT(result,-1,0,all);
for(int i = 0;i < p.size();i++)
for(int j =0;j < all/2;j++)
finalresult.get(i).set(j,finalresult.get(i).get(j)/all);
for(int i = p.size()-2;i > 0;i--) {
out.print(finalresult.get(i).get(0));
out.print(",");
}
out.print(finalresult.get(0).get(0));
out.close();
}
public static void Input(){
try {
a = new ArrayList<ArrayList<Integer>>();
b = new ArrayList<ArrayList<Integer>>();
File file = new File("D:/项目文件/PWData/cai/pw2017-08-23 101950.txt");
Scanner s = new Scanner(file);
all = 2*Integer.parseInt(s.nextLine())+2;
String[] t1,t2;
String str = s.nextLine();
t1 = str.split(",");
str = s.nextLine();
t2 = str.split(" ");
//建立矩阵
for(String s1 : t1){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(Integer.parseInt(s1));
for(int i=0; i<all/2-1; i++) list.add(0);
a.add(0, list);
}
ArrayList<Integer> tempalist1 = new ArrayList<Integer>();
for(int i = 0;i < all/2;i++) tempalist1.add(0);
for(int i = 0;i < t2.length;i++) a.add(tempalist1);
for(String s2 : t2){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(Integer.parseInt(s2));
for(int i = 0;i < all/2-1;i++) list.add(0);
b.add(0,list);
}
ArrayList<Integer> tempalist2 = new ArrayList<Integer>();
for(int i = 0;i < all/2;i++) tempalist2.add(0);
for(int i = 0;i < t1.length;i++) b.add(tempalist2);
} catch (FileNotFoundException e) {
System.out.print("输出结果到result.txt时发生错误!\n");
}
}
}