题意:在一个n*n的棋盘上放m个车,使得各个车之间不相互攻击。有多少种放法?
组合数学解法
现在n行中选出m行,C(n,m),再在n列中选出m列随便放A(n,m),答案为C(n,m)*A(n,m)。
#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: %I64d\n",i, ans); } return 0; }