LightOJ 1005 （数学组合问题）

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=96545#problem/A

Description：

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for rook R₁ from its current position. The figure also shows that the rook R₁ and R₂ are in attacking positions where R₁ and R₃ are not.R₂ and R₃ are also in non-attacking positions.

Now, given two numbers n and k, your job is to determine the number of ways one can put k rooks on an n x n chessboard so that no two of them are in attacking positions.

Input：

Input starts with an integer T (≤ 350), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 30) and k (0 ≤ k ≤ n²).

Output：

For each case, print the case number and total number of ways one can put the given number of rooks on a chessboard of the given size so that no two of them are in attacking positions. You may safely assume that this number will be less than 10¹⁷.

Sample Input：

1 1

2 1

3 1

4 1

4 2

4 3

4 4

4 5

Sample Output：

Case 1: 1

Case 2: 4

Case 3: 9

Case 4: 16

Case 5: 72

Case 6: 96

Case 7: 24

Case 8: 0

题意：有一个棋盘，可以在上面放棋子，不过在放的时候有要求（任意两个棋子不可以在同一行或者同一列），给出n*n的棋盘，问放num个棋子有多少方法可以满足要求。

结合了数学中组合数和找规律来想，可以得到该式：ans = n*n * （n-1）*（n-1） * 。。。。。/num！，由于数比较大，会出现溢出，所以中间需要先约分再乘。。。（第一眼觉得是搜索，发现n是30，不能啊，超时是肯定的。。）

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;

const int N=1e5+10;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int main ()
{
    int T, num, n, k = 0, i, j, vis[100], cou;
    long long ans;

    scanf("%d", &T);

    while (T--)
    {
        k++;
        ans = 1;
        memset(vis, 0, sizeof(vis)); ///记录该数是否被约分

        scanf("%d%d", &n, &num);

        if (num > n) ///每行每列都不能存在两个棋子，那么一旦棋子个数大于行数，肯定不能放棋子
        {
            printf("Case %d: 0
", k);
            continue;
        }

        for (i = n; i >= n-num+1; i--)
        {
            cou = 0; ///记录i能否找到可以约分的数
            for (j = num; j >= 2; j--)
            {
                if (!vis[j] && i % j == 0) ///当j还没有被约分，且i可以与j约分，此时记录
                {
                    cou = 1;
                    vis[j] = 1;
                    ans *= i/j;
                    break; ///找到一个就行，因为j是从最大的开始循环的，那么找到的那个约数肯定是最大的
                }
            }

            ans *= i; ///由于分子是平方，所以需要再乘以i
            if (!cou) ans *= i; ///如果没有找到可以约分的数，需要再乘以i
        }

        for (j = 2; j <= num; j++) ///最后那些没有被约掉的分母，还要除掉
            if (!vis[j]) ans /= j;

        printf("Case %d: %lld
", k, ans);
    }

    return 0;
}