package yukicoder; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solver(); } void solver() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] a = new int[N]; int[] b = new int[N]; for (int i = 0; i < N; i++) { a[i] = sc.nextInt(); } for(int i=0;i>> 1; int bs = nt; double wRe = 1.0; double wIm = 0.0; double uRe = Math.cos(Math.PI / bs); double uIm = -Math.sin(Math.PI / bs); for(int t = 0;t < nt;t++){ for(int j = t; j < n;j += s){ int jp = j + bs; double re = dstRe[jp]*wRe - dstIm[jp]*wIm; double im = dstRe[jp]*wIm + dstIm[jp]*wRe; dstRe[jp] = dstRe[j] - re; dstIm[jp] = dstIm[j] - im; dstRe[j] += re; dstIm[j] += im; } double nwRe = wRe*uRe - wIm*uIm; double nwIm = wRe*uIm + wIm*uRe; wRe = nwRe; wIm = nwIm; } } return new double[][]{dstRe, dstIm}; } protected static int[] reverseBitOrder(int n) { int[] ret = new int[n]; ret[0] = 0; for(int i = 1, h = n>>1;i < n;i <<= 1, h >>>= 1){ for(int j = 0;j < i;j++){ ret[j+i] = ret[j] + h; } } return ret; } public static int[] convolute(int[] a, int[] b) { int m = Integer.highestOneBit(a.length|b.length)<<2; prepareFFT(m); double[][] fa = doFFFT(a, m); double[][] fb = doFFFT(b, m); double[][] fced = new double[2][m]; for(int i = 0;i < m;i++){ fced[0][i] = (fa[0][i]*fb[0][i]-fa[1][i]*fb[1][i])/m; fced[1][i] = (fa[0][i]*fb[1][i]+fa[1][i]*fb[0][i])/-m; } double[][] ced = doFFFT(fced[0], fced[1]); int[] ret = new int[m]; for(int i = 0;i < m;i++){ ret[i] = (int)Math.round(ced[0][i]); } return ret; } static int[] rev; static double[] coss; public static void prepareFFT(int n) { rev = reverseBitOrder(n); coss = new double[n+1]; for(int i = 0;i <= n>>>1;i++){ coss[n-i] = coss[i] = Math.cos(Math.PI*i/(n>>>1)); } } public static double[][] doFFFT(int[] srcRe, int n) { int m = srcRe.length; double[] dstRe = new double[n]; double[] dstIm = new double[n]; for(int i = 0;i < n;i++){ if(rev[i] < m){ dstRe[i] = srcRe[rev[i]]; } } for(int s = 1;s <= n;s <<= 1){ int nt = s >>> 1; int bs = nt; for(int t = 0;t < nt;t++){ double wRe = coss[t*(n/s)]; double wIm = coss[(n>>>2)+t*(n/s)]; for(int j = t; j < n;j += s){ int jp = j + bs; double re = dstRe[jp]*wRe - dstIm[jp]*wIm; double im = dstRe[jp]*wIm + dstIm[jp]*wRe; dstRe[jp] = dstRe[j] - re; dstIm[jp] = dstIm[j] - im; dstRe[j] += re; dstIm[j] += im; } } } return new double[][]{dstRe, dstIm}; } public static double[][] doFFFT(double[] srcRe, double[] srcIm) { int n = srcRe.length; double[] dstRe = new double[n]; double[] dstIm = new double[n]; for(int i = 0;i < n;i++){ dstRe[i] = srcRe[rev[i]]; dstIm[i] = srcIm[rev[i]]; } for(int s = 2;s <= n;s <<= 1){ int nt = s >>> 1; int bs = nt; for(int t = 0;t < nt;t++){ double wRe = coss[t*(n/s)]; double wIm = coss[(n>>>2)+t*(n/s)]; for(int j = t; j < n;j += s){ int jp = j + bs; double re = dstRe[jp]*wRe - dstIm[jp]*wIm; double im = dstRe[jp]*wIm + dstIm[jp]*wRe; dstRe[jp] = dstRe[j] - re; dstIm[jp] = dstIm[j] - im; dstRe[j] += re; dstIm[j] += im; } } } return new double[][]{dstRe, dstIm}; } }