Rooks LightOJ

题意：在n*n的矩形上放k个车，使得它们不能互相攻击，求方案数。

ans[i][j]表示在i*i的矩形上放j个车的方案数。

那么，首先要在(i-1)*(i-1)的矩形上放j-1个，再在比(i-1)*(i-1)多出来的一行一列上放。这多出来的一行一列不是指最下最右的那个，而是以任意方式插入进(i-1)*(i-1)。共有i*i种插入方式。插入之后，在插入的一行一列的交点处放一个车。列几个例子可以发现，这样子产生的方法，每种会重复j次。

组合数学的方法（感觉更正常）：http://blog.csdn.net/guard_mine/article/details/46351445

错误记录：

ans[i][1]=i*i;
for(j=2;j<=i;j++)
    ans[i][j]=ans[i-1][j-1]*i*i/j;

 1 #include<cstdio>
 2 typedef long long LL;
 3 LL ans[31][1000];
 4 LL n,k;
 5 int main()
 6 {
 7     LL i,j,TT,T;
 8     ans[1][1]=ans[1][0]=1;
 9     for(i=2;i<=30;i++)
10     {
11         ans[i][0]=1;
12         for(j=1;j<=i;j++)
13             ans[i][j]=ans[i-1][j-1]*i*i/j;
14     }
15     scanf("%lld",&T);
16     for(TT=1;TT<=T;TT++)
17     {
18         scanf("%lld%lld",&n,&k);
19         printf("Case %lld: %lld
",TT,ans[n][k]);
20     }
21     return 0;
22 }