srm 227 div2 1000pts

这题如果用暴力的方法的话，其实是求排列组合的值。
但是要注意的是做连乘积的时候会发生溢出，因此这里可用BigInteger 来做这些操作。
代码如下：

import java.io.*;
import java.util.*;
import java.util.regex.*;
import java.math.*;

public class TreePlanting {
   public long countArrangements(int total, int fancy) {
		long ans=0;
		int plain=total-fancy+1;
		BigInteger l1=BigInteger.ONE;
		BigInteger l2=BigInteger.ONE;
		for(int i=0;i<fancy;i++){
			l1=l1.multiply(new BigInteger((plain-i)+""));
		}
		for(int i=0;i<fancy;i++){
			l2=l2.multiply(new BigInteger((fancy-i)+""));
		}

		ans=l1.divide(l2).longValue();
		
		return ans;
   }
}

不用BigInteger也是可能的，实际上要使乘积不溢出，只要每次求两个数的gcd，化简即可。
代码如下：

import java.io.*;
import java.util.*;
import java.util.regex.*;
import java.math.*;

public class TreePlanting {
   public long countArrangements(int total, int fancy) {
		long ans=1;
		int plain=total-fancy+1;
		int[] factors=new int[fancy];
		Vector<Integer> vec=new Vector<Integer>();
		for(int i=0;i<fancy;i++){
				factors[i]=fancy-i;
		}
		
		for(int i=0;i<fancy;i++){
			int p=plain-i;
			for(int j=0;j<fancy;j++){
				if(p==1)
					break;
				if(factors[j]==1)
					continue;	
				int g=gcd(p,factors[j]);
				p=p/g;
				factors[j]=factors[j]/g;
			}
			vec.add(p);
		}
		
		for(int i:vec){
			ans*=i;
		}
		
		return ans;
   }
   
   public int gcd(int m,int n){
		  if(n==0) 
		     return m;
		   else 
		     return gcd(n,m%n);
	}
}