HDU 1267 下沙的沙子有几粒？
思路来自：http://www.cnblogs.com/jiangjing/archive/2013/01/18/2866168.html
思路：递推公式为：a[m][n]=a[m-1][n]+a[m][n-1];然后当n=0的时候无论m取何值都是1，递推公式怎么推来的呢？我现在说下我的思路吧！假设3个H和2个D是由2个H和2个D还有3个H一个D推来的，2个H和2个D总共有H D H D，H H D D两种排列，3个H和一个D总共有H D H H,H H D H,H H H D三种排列，然后在H D H D，H H D D的后面添加一个H就是2中排列，在H D H H,H H D H,H H H D的后面添加一个D就有3种方案，所以总共就是5种方案（其它的添加方法都是重复的，不信的话自己可以试一下）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <sstream>
#include <vector>
using namespace std;
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define REPD(i,a,b) for(int i=a;i>=(int)b;i--)typedef long long LL;
LL d[21][21];
LL DP(int m,int n){LL& ans=d[m][n];if(ans!=-1) return ans;if(m==0||m<n) return ans=0;if(n==0) return ans=1;return ans=DP(m-1,n)+DP(m,n-1);
}
int main()
{// freopen("input.in","r",stdin);int m,n; memset(d,-1,sizeof(d));while(scanf("%d%d",&m,&n)==2&&m+n){printf("%I64d\n", DP(m,n));}return 0;
} HDU 1133 Buy the Ticket 递推
与HDU1267相比就是有了次序，要乘以m! * n!
因为是很大的数，所以直接上高精度
import java.util.*;
import java.math.*;
import java.text.*;
import java.io.*; public class Main
{public static void main(String[] args) {Scanner cin=new Scanner(new BufferedInputStream(System.in));int kase=1;BigInteger[] fac=new BigInteger [100+5];BigInteger[][] d=new BigInteger [100+5][100+5];fac[0]=fac[1]=BigInteger.ONE;for(int i=2;i<=100;i++) fac[i]=fac[i-1].multiply(BigInteger.valueOf(i));for(int i=0;i<=100;i++) Arrays.fill(d[i],BigInteger.ZERO);for(int i=0;i<=100;i++) d[i][0]=BigInteger.ONE;for(int i=1;i<=100;i++) for(int j=1;j<=i;j++) d[i][j]=d[i-1][j].add(d[i][j-1]);boolean first=true;while(cin.hasNext()){int m=cin.nextInt(), n=cin.nextInt();if(m==0&&n==0) break;System.out.println("Test #"+kase+":"); kase++;System.out.println(d[m][n].multiply(fac[m]).multiply(fac[n]));}}
}