考新郎 (1023)

https://www.nowcoder.com/pat/2/problem/279 1023 考新郎

知识点：高中知识中的 排列和组合
&&：
1.排列的定义及其计算公式：
从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m）表示。

A(n,m)=n(n-1）（n-2）……（n-m+1）= n!/(n-m)! 此外规定0!=1

2.组合的定义及其计算公式：
从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。

C(n,m)=A(n,m）∧2/m!=A(n,m)/m！；  C(n,m)=C(n,n-m）。（其中n≥m)

思路：
根据错选的人数判断，运用相关数学知识。（重在两个函数）
**: 排列和组合的结果超出int的范围，需要long long。
&&：
1.组合的函数C(n,m)

long C(int n,int m)
{
    int i;
    long long a=1;
    long long b=1;
    for(i = n; i >= 1; i--)
    {
        if(i >= n - m + 1)
            a *= i;
        if(i <= m)
            b *= i;
    }
    long long c = a / b;
    return c;
}

2.排列的函数A(n,m)

long long A(int n, int m)
{
    if(m == 1)
        return n;
    if(m == n)
        return 1;
    return n * A(n - 1, m);
}

3.排列全错推理
1 2 3 4 5 6 ......
0 1 2 9 44 265 ......

long long fun(int n)
{
    if(n == 1)
        return 0;
    if(n == 2)
        return 1;
    return (n - 1) * ( fun(n - 1) + fun(n - 2));
}

牛客AC代码：

#include <cstdio>
#include <cstdlib>

int C(int n,int m);
long long fun(int);
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m) != EOF)
    {
        printf("%lld\n", C(n , n-m) * fun(m));
    }
    return 0;
}
int C(int n,int m)
{
    int i;
    long long a=1;
    long long b=1;
    for(i = n; i >= 1; i--)
    {
        if(i >= n - m + 1)
            a *= i;
        if(i <= m)
            b *= i;
    }
    long long c = a / b;
    return c;
}
long long fun(int n)
{
    if(n == 1)
        return 0;
    if(n == 2)
        return 1;
    return (n - 1) * ( fun(n - 1) + fun(n - 2));
}