Combination DP
这道题目是APAC2015 RoundB 的ProblemA https://code.google.com/codejam/contest/4214486/dashboard，
也是NEU ACM的一道月赛题 http://acm.neu.edu.cn/hustoj/problem.php?id=1447
并且从这里学习了一下Stirling数，之前其实看过，是离散数学课跳过的内容，还有Catalan数，这两个组合数都是非常重要的，Catalan数
1/(n+1) C(2n, n) 是n对括号合法序列数，BOP上买票问题，二叉树个数等等重要的计数问题答案，Striling数相对运用不是特别广泛，
例如第一类是指一个n阶permutation可以由k个轮换乘积表示的个数，第二类是n个数划分为k个非空集合的划分方法，
二者都是通过递推公式来算的，当然也可以直接有对应的通项公式，但是非常复杂。
一开始看一篇博客，说的第一类Striling数，然后底下一哥们评论说是APAC这题，现在清楚了，他说错了，其实不是的，但是也是类似的递推公式。
DP其实就是递推，找出递推式，对于二维状态来说，多半是dp(i,j) 与dp(i-1, j), dp(i, j-1), dp(i-1, j-1) 发生纠葛，然后至于选哪几个，系数是多少
就是数学的brainstorm了，可以先看看子问题dp(i,j) 表示前j个位置放置i种数字的计数，前j-1个位置放置i种和i-1种， 如果放置了i种的话，最后一个任意放
i种的一种，idp(i,j-1), 如果是放置了i-1种数字，那么最后一个位置只能放置剩下的一种，但是前面i-1是i种里面的哪i-1种，C(i,i-1)=i, 所以idp(i-1,j-1)
因此得到dp(i,j)=i(dp(i-1,j)+dp(i-1,j-1)),i<j, i=1…m, j=1…n, m<=n, 需要设置base，dp(1,j)=1, dp(i,i)=i!,
注意对于这种溢出的情况，MOD一个大数，这个数是1e9+7,int范围内，但是(1e9+7)100可能是超过int 范围的，因此用long long(10^18),递推式也不会超过LL范围，
因此代码如下：
LL dp[maxn][maxn];
const LL MOD=1e9+7;
int main()
{
#ifndef ONLINE_JUDGE
freopen ("A-large-practice.in" , "r" , stdin);
freopen ("A-large-practice.out" , "w" , stdout);
#endif
LL t;
cin>>t;
for(LL ti=1;ti<=t;ti++)
{
LL m, n;
cin>>m>>n;//m<=n
for(LL j=1;j<=n;j++) dp[1][j]=1ll;
for(LL i=2;i<=m;i++) dp[i][i]=(dp[i-1][i-1]*i)%MOD;
for(int i=2;i<=m;i++) for(int j=i+1;j<=n;j++)
dp[i][j]=(i*(dp[i][j-1]+dp[i-1][j-1]))%MOD;
printf("Case #%d: ",ti);
cout<<dp[m][n]<<endl;
}
return 0;
}
代码如下，感觉这道是四次APAC ProblemA里最难的，其他的两道编程题，一道DFS，都比较make sense