http://acm.timus.ru/problem.aspx?space=1&num=1476
由于前一列对后一列有影响，所以需要保持前一列的状态，
但无需用状态压缩来保存（也保存不了） 只需要保存前一列以 k 个0结尾的个数就可以
代码：
import java.math.BigInteger;
import java.util.Scanner; public class Main { /**
* @param args
*/
static final int N = 44;
public static void main(String[] args) {
// TODO Auto-generated method stub
BigInteger[][] dp = new BigInteger[N][N];
BigInteger[][] d = new BigInteger[N][N];
BigInteger[][] c = new BigInteger[N][N];
for(int i=0;i<N;++i){
for(int j=0;j<N;++j){
dp[i][j]=d[i][j]=c[i][j]=BigInteger.ZERO;
}
}
for(int i=0;i<N;++i){
for(int j=0;j<=i;++j){
if(j==0||i==j){
c[i][j]=BigInteger.ONE;
}
else{
c[i][j]=c[i-1][j].add(c[i-1][j-1]);
}
}
}
Scanner in = new Scanner(System.in); int n=in.nextInt();
int m=in.nextInt();
int k=in.nextInt(); for(int i=0;i<=n;++i){
for(int j=0;j<=i;++j){
for(int l=0;l<=(n-i);++l){
if(i-j<=k){
d[i][j+l]=d[i][j+l].add(c[i][j].multiply(c[n-i][l]));
}
}
}
}
dp[0][0]=BigInteger.ONE;
BigInteger ans=BigInteger.ZERO;
for(int i=0;i<=m;++i){
for(int j=0;j<=n;++j){
if(i==m){
ans=ans.add(dp[i][j]);
continue;
}
for(int l=0;l<=n;++l){
dp[i+1][l]=dp[i+1][l].add(dp[i][j].multiply(d[j][l]));
}
}
}
System.out.println(ans); }
}