Rooks---LightOj1005(排列组合)

题目链接：http://lightoj.com/volume_showproblem.php?problem=1005

题意就是在一个n*n的方格中放k个棋子，每一行每一列都不能有两个棋子，问有多少种方法，和8皇后问题很像， 但是8皇后问题可以用暴力搜索，但是本题n的取值范围较大，不能用搜索；在比赛的时候我找到了公式，但是由于乘除的顺序问题导致错误；就是A（n，k）*A（n，k）/ A（k，k）；即C（n， k）*A（n， k）；

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

using namespace std;

#define N 4000100

int main()

{

    int T, t=;

    int n, m;

    long long ans;

    scanf("%d", &T);

    while(T--)

    {

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

        ans = ;

        for(int i=n; i>n-m; i--)

            ans*=i;

        for(int i=; i<=m; i++)

            ans/=i;

        for(int i=n; i>n-m; i--)

            ans*=i;

        printf("Case %d: %lld\n", t++, ans);

    }

    return ;

}

还有一种方法是dp：

#include<stdio.h>

#include<string.h>

int main()

{

    int T, n, m, t=;

    long long dp[][];

    memset(dp, , sizeof(dp));

    for(int i=; i<=; i++)

        dp[i][] = ;

    for(int i=; i<; i++)

    {

        for(int j=; j<=i*i; j++)

        {

            dp[i][j] = dp[i-][j] + dp[i-][j-]*(*i-*j+) + dp[i-][j-]*((i-j+)*(i-j+));

        }

    }

    scanf("%d", &T);

    while(T--)

    {

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

        printf("Case %d: %lld\n", t++, dp[n][m]);

    }

    return ;

}