​【java】蓝桥杯——小蓝与钥匙_全错排列​

 题目链接：小蓝与钥匙

问题描述

小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了 一个游戏。

小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房 间对应一把钥匙, 每把钥匙只能打开自己的门。现在小蓝让这 28 个孩子分别将 自己宿舍的钥匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 28!=28×27×⋯×128!=28×27×⋯×1 种分配方案。小蓝想知道这些方案中, 有多少种方案恰有 一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙, 有 14 个孩子分到的不是自己房间的钥匙)。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

 题目分析

先从28个人选定14个人拿直接的钥匙，再进行全错排列：14个人拿的钥匙都不是自己的

全错排列公式：D(n) = (n-1) [D(n-2) + D(n-1)]

递推推导过程

当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.

• 第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

• 第二步，放编号为k的元素，这时有两种情况：
  ⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；
  ⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；

• 综上得到
  D(n) = (n-1) [D(n-2) + D(n-1)]
  特殊地，D(1) = 0, D(2) = 1

•  贴一个链接

  错排问题(全错排)_不想悲伤到天明的博客-CSDN博客

题目代码 

public class 小蓝与钥匙 {

    public static void main(String[] args) {
        long a = 14;
        long m = 14;
        long n = 28;
        long res = D(a) * pailie(n, m);
        System.out.println(res);
    }

    //全错排列 14
    public static long D(long a) {
        if (a == 0 || a == 1) {
            return 0;
        }
        if (a == 2) {
            return 1;
        }
        return (a - 1) * (D(a - 1) + D(a - 2));
    }

    //C 28 14
    public static long pailie(long n, long m) {
        long res = 1l;
        for (int i = 0; i < m; i++) {
            res = res * (n - i) / (i + 1);
        }
        return res;
    }
}