結果

問題 No.387 ハンコ
コンテスト
ユーザー 37zigen
提出日時 2016-07-02 00:18:56
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 4,002 bytes
コンパイル時間 2,383 ms
コンパイル使用メモリ 77,392 KB
実行使用メモリ 78,084 KB
最終ジャッジ日時 2024-10-12 01:35:50
合計ジャッジ時間 21,199 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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<N;i++){
			b[i]=sc.nextInt();
		}
		int[] c=convolute(a,b);
		
		for(int i=0;i<2*N;i++){
			if(c[i]%2==0){
				System.out.println("ODD");
			}else{
				System.out.println("EVEN");
			}
		}

	}
	public static double[][] doFFT(double[] srcRe, double[] srcIm)
	{
		int n = srcRe.length;
		if(Integer.bitCount(n) != 1)return null;
		int[] rev = reverseBitOrder(n);
		
		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 = 1;s <= n;s <<= 1){
			int nt = s >>> 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};
	}

	
}
0