题目链接
题意：在一个n*n的棋盘上放m个车，使得各个车之间不相互攻击。有多少种放法？
组合数学解法
现在n行中选出m行，C(n,m)，再在n列中选出m列随便放A(n,m)，答案为C(n,m)*A(n,m)。
代码语言：javascript复制#include <stdio.h>
#include <string.h>
typedef __int64 LL;
LL A(int n, int m)
{
LL ans = 1;
for (int i = n-m 1; i <= n; i )
ans *= i;
return ans;
}
LL C(int n, int m)
{
LL ans = 1;
for (int i = 1; i <= m; i )
ans = ans*(n-i 1)/i;
return ans;
}
int main()
{
int t, m, n;
scanf("%d", &t);
for (int i = 1; i <= t; i )
{
LL ans;
scanf("%d %d", &n, &m);
if (m <= n)
ans = C(n, m)*A(n, m);
else
ans = 0;
printf("Case %d: %I64dn",i, ans);
}
return 0;
}对于这到题来说，状态压缩dp做数据量貌似有点大。
