2020-04-18 17:25 宁波市效实中学 C++

关注

牛客挑战赛39 - 牛牛与序列

牛牛与序列

https://ac.nowcoder.com/acm/contest/5157/E

题意

求长度为 $n$ 的序列 $\{a\}$ ，满足 $1 \le a_i \le k$ ，且存在 $i,j$ 满足 $a_{i-1}<a_i,a_{j-1}>a_j$ ，求序列数量。

算法（ $O(T \log n + \sum k)$ ）

赛时没看这题，以为很难。。。

根据容斥原理，答案为全部-单调不升-单调不降+不升不降。

$ans=k^n-2f_{n,k}+k\\ f_{i,j}=\sum_{k \le j} f_{i-1,k}=f_{i-1,j}+f_{i,j-1}=\frac{(i+j)!}{i!j!}$

第二个式子最后一次化简，可以看作 $i \times j$ 的方格，从左上到右下的路径条数，有 $i$ 次向右， $j$ 次向下，即有重复的排列问题。

$f_{n,k}=\frac{\prod_{i=n+1}^{n+k} i}{k!}$

全部评论

推荐最新楼层

05-16 10:37

已编辑

同济大学 ARM工程师

我动了谁的蛋糕？资本你赢了

之前给加上一个人脸识别。需要有登录，注册，还要调用百度 api，还要一天内弄完 把程序员当成月入 3000 的小丑吗，你放家门口通马桶的工人电话，问一下他疏通一次马桶低于 400 干不干全网最受欢迎的嵌入式面经面经一共32篇文章，12w+字数，包含全部最新的面试必问考点，4.7w+同学学习，2800+订阅，非常适合在找工作面经薄弱的同学，3000+订阅还会涨价，提前订阅提前享受，持续更新中。原帖链接：https://www.nowcoder.com/creation/manager/columnDetail/MJNwoM

弦五Strings：第二个我可以

ai做完cv

点赞评论收藏

昨天 17:11

已编辑

中山大学 Java

暑期实习应该可以暂告一段落了？

本人本 2 硕 9，Java 选手，从 3 月中旬开始投递简历，到目前为止投了六十几家吧，面试了接近三十场，主要是大厂，中小厂要么不推进要么直接挂简历，最后是拿到了拼多多服务端研发的 offer，腾讯面完了 HR 面还没有结果，以下是本人这几个月来的面试情况，希望对大家能有帮助捏，后续也会尽量将每场面试的面经发一下简历/评估挂OPPO快手，投了三次简历，都是简历挂，打算后面挂一次我再投一次百度（招聘人数很少，个位数，挂了也正常吧？）饿了么（笔试 A 了 2.4 / 3）小米高德平头哥阿里国际希音小红书搜狐畅游文远知行阿里巴巴控股滴滴凡岛众安笔试挂网易互娱（150 分钟三道编程...

投递腾讯等公司10个岗位 >

点赞评论收藏

04-29 22:35

门头沟学院 Java

笑了，这就是应届生

#求职#

牛友说改了名字能收到offer：旧图新发

查看图片

点赞评论收藏

05-15 16:51

门头沟学院前端工程师

2024互联网公司工时排行出炉！看看你在第几名。

在选择公司时，"工作时长"是一个至关重要的参考指标。除了关注总收入（package）外，还需考量公司的加班文化是否人性化。工作时长定义周工作小时数：法定标准为40小时（即“955”工作制）。常见工作制折算：大小周：约60小时/周996：约65小时/周其他模式可依此类推。排名依据：基于最近一年公司薪酬数据中工作时长的平均值。数据背景几年前，职级对标平台在薪酬表单中新增了工作时长填报功能，以反映这一决定性指标。经过多年积累，现已汇总出2024年互联网公司工作时长排行榜。通过此榜单，求职者可更全面地评估不同公司的实际工作强度，做出更理性的职业选择。数据仅供参考，如有补充或更正，欢...

牛油的搬砖plog

点赞评论收藏

全站热榜

创作者周榜

正在热议

牛客挑战赛39 - 牛牛与序列

题意

算法（）

全站热榜

创作者周榜

算法（ $O(T \log n + \sum k)$ ）