首页 > 搜索 > BFS搜索 > POJ 2450 A New Kind of Chess [解题报告] Java
2013
11-11

POJ 2450 A New Kind of Chess [解题报告] Java

A New Kind of Chess

问题描述 :

Prince Remmarguts met Uyuw successfully in our previous story, and after that Princess Uyuw introduced a new kind of chess to Remmarguts named Nixgnauhc. The only chessman allowed in it was a special type of Knight.

The chessboard is of (N + 1) * (M + 1). Each of the rows and columns are numbered as the following graph:



Here N + 1 = 5 + 1 is the number of rows and M + 1 = 4 + 1 is the number of columns. We are also given two integer numbers P and Q, and told that at the beginning of the game, the blocks of (x, y) – (row number, column number) – where x <= P and y <= Q are already taken up by Knight.

During the game, we can choose a single Knight to move, and the only allowed movements for Knight at (x, y) is to (x + a, y + b) or to (x + c, y + d). But during the movement, the position it goes must be on the chessboard and NOT be taken up by another Knight. Our purpose is to move that chessman to the final end (N, M). (The description above means that once you choose a chessman, you can only move that chessman in the following steps)

Meanwhile, we suppose 3 <= N, M <= 100000, 0 <= P < N, 0 <= Q < M, 1<= a, b, c, d. Princess Uyuw wanted to know the number of essentially different games. Two games are called “different” if and only if we choose the different chessman at the beginning or perform a different movement at some time.

WARNING: Even if a = c, b = d, we also call (+a, +b) and (+c, +d) DIFFERENT movements!

输入:

You should read the number of test cases Z in the first line – Z <= 100.

Each of the following lines denotes a single test case, consisting of 8 integers N, M, P, Q, a, b, c, and d. The meanings of such integers are described above.

输出:

Output one line per test case, showing the total possibilities of games. We guarantee this number is less than 10^500.

样例输入:

2
3 3 0 0 1 1 1 1
5 4 2 1 1 1 2 1

样例输出:

8
7

解题代码:

//* @author:

import java.util.*;
import java.math.*;

public class Main {
  static int gcd(int a,int b)
  {
	int c;
	while( (a%=b) != 0 )
	{
         c=b;
	  b=a;
	  a=c;
	}
	return b;
   }
	
  static int a,b,c,d,n,m,p,q;
  static int t[] = new int[100001];
	
  static BigInteger comb(int a,int b)
 {
   int i,j,g,k,last;
   if( b > a/2 )
     b = a - b;
   last = b;
	
   for(i=0;i< b;i++)
   {
	t[i]=a-i;
   }
		
   for(i=2;i<=b;i++)
   {
	k=i;
	for(j=0;j< b/*last*/&&k>1;j++)
	if(t[j]>1)
	{
         g=gcd(t[j],k);
	  t[j]/=g;
	  k/=g;
	}
    }
					
    BigInteger ans = BigInteger.valueOf(1);
    int temp=1;
    for(i=0;i< last;i++)
	if(t[i]>1)
	{
	  temp*=t[i];
	  if(temp>=10000)
	  {
	    ans=ans.multiply( BigInteger.valueOf(temp) );
	    temp=1;
	   }
	}
		
    ans=ans.multiply( BigInteger.valueOf(temp) );
    return ans;
   }

   static void doit()
   {
     int x1,x2,n1,m1,n2,m2,temp1,temp2, temp;
     boolean key;
     BigInteger ans = BigInteger.valueOf( 0 );
     if( (int)(((n-p)/a)< ((m-q)/b)?((n-p)/a):((m-q)/b)) > 
	(int)(((n-p)/c)< ((m-q)/d)?((n-p)/c):((m-q)/d)) ) 
     {
	temp = a; a = c; c = temp;
	temp = b; b = d; d = temp;
     }
		
    for( x1=0 ; (n1=n-a*x1)>=0 && (m1=m-b*x1)>=0 ; x1++ )
    {	
	temp1=(n1>p) ? (n1-p+c-1)/c : 0;
	temp2=(m1>q) ? (m1-q+d-1)/d : 0;
	x2 = temp1>temp2 ? temp1 : temp2 ;
	n2 = n1-c*x2; m2 = m1-d*x2;
	while( n2>p&&m2>q )
         System.out.println( "error" );
						
	key = true;
	while( n2>=0 && m2>=0 && key )
	{
	   key = false;
	   if( x1 != 0 && ( n2 + a > p || m2 + b > q ) ) {
		ans = ans.add( comb( x1+x2-1, x1-1 ) );
		key = true;
	   }
						
	 if( x2 != 0 && ( n2 + c > p || m2 + d > q ) ) {
	   ans = ans.add( comb( x1+x2-1, x2-1 ) );
	   key = true;
	}
				
	n2 -= c;
	m2 -= d;
	x2++;
    }
   }
		
   System.out.println( ans );
	//ans.output('\n');
  }

  public static void main( String [] str )
  {
	int cas;
	Scanner cin = new Scanner( System.in );
	cas = cin.nextInt();
	while( cas-- != 0 )
	{	
        n = cin.nextInt();
	 m = cin.nextInt();
	 p = cin.nextInt();
	 q = cin.nextInt();
	 a = cin.nextInt();
	 b = cin.nextInt();
	 c = cin.nextInt();
	 d = cin.nextInt();
	doit();
	}
	return;
  }
}