結果

問題 No.474 色塗り2
ユーザー uwi
提出日時 2016-12-24 00:11:45
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 335 ms
コード長 3,966 Byte
コンパイル時間 6,402 ms
使用メモリ 82,012 KB
最終ジャッジ日時 2019-07-16 21:45:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 222 ms
67,140 KB
2.txt AC 232 ms
66,300 KB
3.txt AC 222 ms
66,800 KB
large1.txt AC 335 ms
82,012 KB
sample.txt AC 224 ms
67,532 KB
テストケース一括ダウンロード

ソースコード

diff #
package adv2016;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class N474 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		long[] fs = new long[3000005];
		int[] es = new int[3000005];
		fs[0] = 1;
		long mod = 1L<<20;
		for(int i = 1;i < fs.length;i++){
			int j = i;
			es[i] = es[i-1];
			while(j % 2 == 0){
				j /= 2;
				es[i]++;
			}
			fs[i] = fs[i-1] * j % mod;
		}
		
		for(int T = ni();T > 0;T--){
			int a = ni(), b = ni(), c = ni();
			if(c % 2 == 0){
				out.println(0);
			}else{
				int e = es[b+c-1] - es[c-1] - es[b];
				long cv = fs[b+c-1] * invl(fs[c-1], mod) % mod * invl(fs[b], mod) % mod;
				if(e >= 20){
					cv = 0;
				}else{
					cv = (cv<<e)%mod;
				}
				cv = cv * c % mod;
				cv--;
				if(cv < 0)cv += mod;
				if((a&cv) != 0){
					out.println(0);
				}else{
					out.println(1);
				}
			}
		}
	}
	
	public static long invl(long a, long mod) {
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new N474().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
0