简单的划分数问题I(高精度)

简单的划分数问题(高精度)

 Memory Limit:65536K

Total Submit:6 Accepted:5

Description

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。

Input

连续输入n,k(为了简化问题，假设n<=1000,k<=200&&n>k) 如果输入n和k都为0就结束。

Output

一个整数，即不同的分法。

Sample Input

7 3      

1000 20

0 0

Sample Output

4      

15374874902418364055409

代码：

package ac0901;
import java.util.*;
import java.io.*;
import java.math.*;
import java.math.BigInteger;
public class ac0901 
{
  public static void main(String args[])
  {
    Scanner cin=new Scanner(System.in);
    int i,j, n,k;
    BigInteger fac[][]=new BigInteger[1010][210];
    for(i=0; i<=1000; ++i)
    {
      for(j=0; j<=200; ++j)
      {
        fac[i][j]=BigInteger.ZERO;
        fac[0][0]=BigInteger.ONE;
      }
    }
    for(i=1; i<=1000; ++i)
    {
      for(j=1; j<=200; ++j)
      {
        if(j<=i) fac[i][j]=fac[i-1][j-1].add(fac[i-j][j]);
      }
    }
    while(cin.hasNext())
    {
        n=cin.nextInt();
        k=cin.nextInt();
        if(n==0&&k==0) break;
          System.out.println(fac[n][k]);
    }
  }
}