23春招华为最难的一道题，你会做吗？来挑战一下吧！

航旅王谦

关于22年华为机考

​   22年秋招期间(8月~11月)，华为基本每周三晚7点准时开两个小时的笔试。三道题，分数为100,200,300。达到150分就能过机试。当然越高越好。一般第一题是偏模拟的题，第二三题是传统算法题。常考二分，动态规划，DFS,BFS等知识点。面试阶段也会对你的机试题目的代码进行复盘。不过基本都不会问的很深。就问问整体思路是啥，你写的各个函数的功能是什么。面试分三个阶段，前两个阶段也都会有手撕代码。不过80%的情况下都是直接给力扣原题!
​   这里吐槽一句，华为是真爱做题。因为就算你进去华子之后还有华为可信考试等着你们。科目一又是经典的算法题。一个月有一次考试机会。分三个级别，入门级，工作级，专业级。其中专业级的最后一题差不多能到力扣hard的难度。
真题以及在线评测

​   去年华为机考的真题以及提交网址:codefun2000 , 上面大概有10多道。我手上还捏着50多道没放到OJ里。大家敬请期待！(鸽
进入正题

​   今天要与大家分享的是我认为去年机考所有题目中难度最高的一道题。拿到ACM区域赛中也能算是一个铜牌题了。要想在1个小时内分析完成并满分通过还是有一定的挑战。但是它当时被放在了第一题,只值100分...
花圃种植

有 M 块花圃(使用 0,1,2,...,M-1 方式连续编号)，每种植物(植物使用 0,1,2,...,N-1 方式连续编号)需要种植到其中一块花圃上 ，
要求植物编号除以总花圃数的余数不能与所种植的花圃编号相同，种植方案要满足种植的花圃数目尽量多，多个花圃中的植物不能重样。
请编写一个程序， 统计所有满足条件的种植方案数目。
输入描述

输入为两个整数花圃数目 M 和 植物数量 N 。
1 \leq M \leq 1000 , 1 \leq N \leq 10000
输出描述

输出满足条件的种植方案数目
样例

输入
2 3输出
2------------------------------------------------题解分割--------------------------------------------

------------------------------------------------题解分割--------------------------------------------

------------------------------------------------题解分割--------------------------------------------

题目思路

1.前置知识:错排原理的容斥解法: 错排数 = 所有排列的个数 - 至少存在一个对位的排列个数 +  至少存在两个对位的排列个数 -  至少存在三个对位的排列个数 + ...
即  D(n) = n! - C_{n}^{1}(n - 1)! + C_{n}^{2}(n - 2)!  -... +(-1)^n C^{n}_{n} 0!  2.考虑一个简单情况:当 n = m  这就是一个错排问题。
3.当$n < m$时 ， 显然可以沿用容斥方法得出公式:  D(m , n) = A_{m}^{n} - C_{n}^{1}A_{m - 1}^{n - 1} + C_{n}^{1}A_{m - 1}^{n - 1} - ... + (-1)^n C_{n}^{n}A_{m - n}^{0}  4.当 n > m 时，情况会比较复杂：
举个例子： n = 4,  m = 2 ，如下图所示:
合法的排列就是:
(1 , 0) , (1 , 2), (1 , 3), (2 , 0), (2 , 1), (2 , 3)
不难看出，就是每个位置可能会有多个数产生对位的情况 , 我们还是延续刚才的容斥原理的想法往下推导：(以上面的为例)
总排列数显然是: A_{4}^{2}
至少有一个对位:
​   对位产生在0号位：0或者2 放在第0号位,其他3个随意排
​   对位产生在1号位：1或者3 放在第1号位，其他3个随意排
至少有两个对位:
​   对位同时产生在0,1号位上:有 2 \times 2 种情况
这个例子稍微简单一些，请自己分析更复杂的情况: n = 7 , m = 3
分析清楚之后我们令第 i 个花圃能够放的植物个数为 a_i = [n / m] + [n \% m \leq i] ， 那么容斥的系数$b_i$为所有子集的乘积的和  \Large b_i = \sum_{在a序列中取尽大小为i的子集S} \prod_{j \in S}^{} a_j  这个东西用动态规划求解:
令 dp_{i,j} 代表前 i 个数,从中选出一个大小为j的子集的乘积的和。有转移  dp_{i,j} = dp_{i-1,j} + dp_{i-1,j-1} * a_i  至此，总答案为:  ans = A_{n}^{m} - dp_{m,1}A_{n-1}^{m-1} + dp_{m,1}A_{n-1}^{m-1} - ... + (-1)^m dp_{m,m}A_{n-m}^{0}   由于题目没有要求取模，则需要使用高精。
代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static BigInteger A(int n, int m) {      //计算排列数
        BigInteger res = new BigInteger("1");
        for(int i = n ; i >= n-m+1 ; i --) {    //A(n,m) = n*(n-1)*...*(n-(m-1))
            res = res.multiply(new BigInteger(String.valueOf(i)));
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(), n = in.nextInt();
        BigInteger[] a = new BigInteger[m + 5];
        for (int i = 0; i < a.length; i++) {    //初始化数组
            a = new BigInteger("0");
        }
        for (int i = 0 ; i < n ; i++){          //初始化每种植物的个数
            a[i % m + 1] = a[i % m + 1].add(new BigInteger("1"));
        }
        BigInteger [][] dp = new BigInteger[m + 5][m + 5];  
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {        //初始化dp数组
                dp[j] = new BigInteger("0");
            }
        }
        dp[0][0] = new BigInteger("1");     //初始化起始值
        for (int i = 1 ; i <= m ; i++){
            dp[0] = new BigInteger("1");
            for (int j = 1 ; j <= i ; j++){
                dp[j] = dp[i - 1][j - 1].multiply(a).add(dp[i - 1][j]);
            }
        }
        if(n < m) {
            int t = n;
            n = m;
            m = t;
        }
        BigInteger ans = A(n, m);
        for (int i = 1 ; i <= m ; i++){
            BigInteger res = A(n-i, m-i).multiply(dp[m]);
            if (i % 2 == 1) ans = ans.subtract(res);
            else ans = ans.add(res);
        }
        System.out.println(ans);
    }
}

我们一直在将收集到的机试真题制作数据并搬运到OJ上，供大家免费练习,体会真题难度。现在已录入100+道2022/23年最新大厂真题，同时在不断的更新。关注我们的OJ与相关社群获得每道题的题解+代码，并与群大佬们分享求职经历！