关注
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),由于带模,需要用杨辉三角或乘法逆元提前处理一下组合数。
查看原帖
点赞 评论
相关推荐
查看11道真题和解析 点赞 评论 收藏
分享
2025-12-26 10:52
河北传媒学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习没人带,苟住还是跑路? #
11516次浏览 245人参与
# 你觉得专业和学校哪个对薪资影响最大 #
87302次浏览 587人参与
# 对2025年忏悔 #
3714次浏览 93人参与
# 巨人网络求职进展汇总 #
183740次浏览 1222人参与
# 元旦假期你打算怎么过 #
7647次浏览 164人参与
# 春招前还要继续实习吗? #
4085次浏览 58人参与
# 大家实习都在做什么? #
8181次浏览 87人参与
# 面试官问过你最刁钻的问题是什么? #
8536次浏览 93人参与
# 我们是不是被“优绩主义”绑架了? #
8672次浏览 280人参与
# 一人说一家双休的公司 #
6493次浏览 89人参与
# 新年的第一句祝福 #
50927次浏览 376人参与
# 妈妈治愈了你哪些脆皮时刻 #
38879次浏览 338人参与
# 机械人你觉得今年行情怎么样? #
6285次浏览 88人参与
# 牛客2025仙途报告 #
36162次浏览 476人参与
# 一起聊字节 #
238171次浏览 1014人参与
# 你做过哪些dirty work #
25213次浏览 155人参与
# 如何提高实习转正率? #
73173次浏览 464人参与
# 秋招盘点:机械人值得去的企业 #
93735次浏览 732人参与
# 运营来爆料 #
72522次浏览 454人参与
# 腾讯工作体验 #
548494次浏览 3660人参与
腾讯成长空间 5981人发布