[UVa] 10329 - Combinatorial Expression

題目網址: https://goo.gl/71ydBi

題意:
(from luckycat)


解法:
參考 Morris http://mypaper.pchome.com.tw/zerojudge/post/1326314489。
要利用對數的性質。

TAG: Math, BigNum

注意:

程式碼:

	/**
	* Tittle: 10329 - Combinatorial Expression
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/28
	*/
	import java.util.*;
	import java.math.*;
	public class Main {
	public static final int P = 5000;
	public static ArrayList<Integer> prime = new ArrayList<Integer>();
	public static HashMap<Integer,Integer> p2n = new HashMap<Integer,Integer>();
	public static boolean[] isprime = new boolean[P+5];
	public static ArrayList<ArrayList<Integer>> factNum = new ArrayList<ArrayList<Integer>>();
	public static ArrayList<ArrayList<Integer>> factVal = new ArrayList<ArrayList<Integer>>();
	public static int[] poly = new int[1000];
	public static void main( String[] args ) {
	int N, M;
	int n, r;
	int v;
	int rs;
	double dig;
	BigInteger ans;
	Scanner input = new Scanner(System.in);
	init();
	// input
	while( input.hasNext() ) {
	N = input.nextInt();
	M = input.nextInt();
	for( int i=0; i<prime.size(); ++i )
	poly[i] = 0;
	// solve
	while( N-- > 0 ) {
	n = input.nextInt();
	r = input.nextInt();
	if( n-r < r ) r = n-r;
	calc( n, r, true );
	}
	while( M-- > 0 ) {
	n = input.nextInt();
	r = input.nextInt();
	if( n-r < r ) r = n-r;
	calc( n, r, false );
	}
	// check & output
	rs = 1;
	for( int i=0; i<prime.size(); ++i ) if( poly[i]<0 ) {
	rs = 0;
	break;
	}
	if( rs == 1 ) {
	dig = 0;
	for( int i=0; i<prime.size(); ++i ) if( poly[i]!=0 )
	dig += poly[i]*Math.log10(prime.get(i));
	if( dig >= 100.0 ) rs = -1;
	}
	if( rs == 1 ) {
	ans = BigInteger.ONE;
	for( int i=0; i<prime.size(); ++i ) if( poly[i]!=0 )
	ans = ans.multiply( BigInteger.valueOf(prime.get(i)).pow(poly[i]) );
	System.out.println(ans.toString());
	} else
	System.out.println(rs);
	}
	input.close();
	}
	public static void calc( int n, int r, boolean numerator ) {
	int a = n;
	int b = 1;
	while( r-- > 0 ) {
	for( int i=0; i<factNum.get(a).size(); ++i )
	poly[p2n.get(factVal.get(a).get(i))] += (numerator ? factNum.get(a).get(i):-factNum.get(a).get(i));
	for( int i=0; i<factNum.get(b).size(); ++i )
	poly[p2n.get(factVal.get(b).get(i))] += (numerator ? -factNum.get(b).get(i):factNum.get(b).get(i));
	--a;
	++b;
	}
	}
	public static void init() {
	int tmp, v, cnt;
	// find primes
	for( int i=0; i<=P; ++i )
	isprime[i] = true;
	isprime[0]=isprime[1]=true;
	for( int i=2; i<=P; ++i ) if( isprime[i] ) {
	p2n.put(i,prime.size());
	prime.add(i);
	for( int j=i*i; j<=P; j+=i )
	isprime[j] = false;
	}
	// make factor table
	for( int i=0; i<=P; ++i ) {
	factNum.add( new ArrayList<Integer>() );
	factVal.add( new ArrayList<Integer>() );
	}
	for( int i=2; i<=P; ++i ) {
	tmp = i;
	for( int j=0; j<prime.size(); ++j ) {
	v = prime.get(j);
	if( v*v > tmp ) break;
	cnt = 0;
	while( tmp%v == 0 ) {
	tmp /= v;
	++cnt;
	}
	if( cnt > 0 ) {
	factNum.get(i).add(cnt);
	factVal.get(i).add(v);
	}
	}
	if( tmp != 1 ) {
	factNum.get(i).add(1);
	factVal.get(i).add(tmp);
	}
	}
	}
	}

view raw 10329 - Combinatorial Expression.java hosted with ❤ by GitHub