关注
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),由于带模,需要用杨辉三角或乘法逆元提前处理一下组合数。
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
6093次浏览 92人参与
# 工作中的卑微时刻 #
33386次浏览 199人参与
# 牛客AI体验站 #
16185次浏览 285人参与
# 多益网络工作体验 #
63115次浏览 306人参与
# 有必要和同事成为好朋友吗? #
930次浏览 17人参与
# 正在实习的碎碎念 #
1644733次浏览 13716人参与
# 面试中的破防瞬间 #
1190053次浏览 11026人参与
# 工作一周年分享 #
52292次浏览 274人参与
# 滴!实习打卡 #
786420次浏览 6841人参与
# 秋招吐槽大会 #
304200次浏览 1523人参与
# 机械人的薪资开到多少,才适合去? #
164992次浏览 571人参与
# 你最满意的offer薪资是哪家公司? #
71341次浏览 353人参与
# 大学最后一个寒假,我想…… #
89237次浏览 809人参与
# 哪些公司真双非友好? #
62846次浏览 268人参与
# OC/开奖 #
411200次浏览 2282人参与
# 为了实习逃课值吗? #
65711次浏览 526人参与
# 如果可以选,你最想从事什么工作 #
721829次浏览 4870人参与
# 重来一次,你会对开始求职的自己说 #
32771次浏览 388人参与
# 如何提高实习转正率? #
86471次浏览 504人参与
# 如何确定求职岗位 #
723490次浏览 6427人参与
查看3道真题和解析