京东算法2023/3/4机试编程题目

那个全过的大佬出来指导一下啊，这题咋做呢。

蹲

M

mark一下，首先全排列就是N^N，那么对于N，出现在第一位的次数就是N^(N-1)，一共会出现1-N，因此最大值为N的时候，权值和为N*N^(N-1),同理，当最大值为N-1的时候，N*(N-1)^(N-1),所以结果就是N*(N^(N-1)+(N-1)^(N-1).....1^(N-1)), 比如2就是2*（2^1+1^1）2*(2+1)为6，3就是3*(3^2+2^2+1^2) 3*(9+4+1)为42

1. 首先单独考虑最大值为1.此时只能是[1, 1, 1,...,1]（共n个），其权值为n。 2. 下面考虑最大值不为1。枚举最大值为max，枚举其出现次数为cnt（显然，此时cnt即为权值） --- 2.1 首先，从n个位置中选择cnt个位置填入当前最大值max，这是一个组合问题，其次数为C(n, cnt)，记为t1 --- 2.2 然后，考虑剩余的n-cnt个位置。显然每个位置可以填入1~max-1共max-1种可能的取值。因此为pow(max-1,n-cnt)，记为t2 --- 2.3 上述两步之间是乘法关系，对总答案有cnt*t1*t2的贡献，把全部加到最终答案上即可。 3. 综合1，2，得到解。复杂度为O(n^2)，由于带模，需要用杨辉三角或乘法逆元提前处理一下组合数。