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!}$

全部评论

推荐最新楼层

昨天 11:33

华南理工大学 Java

公司带薪offer要签完三方再发

准备签三方了，公司那边要求三方上写的薪资是实习薪资，而且hr说带薪offer还要签完三方之后才能下来，会不会被坑牛友们能支个招吗

听说改名就会有offer：就是坑

签约/解约注意事项

点赞评论收藏

11-22 17:37

已编辑

江西省吉水县第二中学 Java

数字马力28号oc还没沟通

数码蝶不会真鸽了我吧，学院本就不配嘛oc后我都梭哈了，没去面其他的，结果这样搞还满心欢喜等着电话刷几下牛客直接破防了，这下这么办啊----------------------------------------------------------11.21 更新有大佬拒offer把我捞起来了，接受了长沙offer1月要强制去实习，据说有些部门强度拉满，乐观点至少有工作了

fangfu：社会第一课，不要把鸡蛋放一个篮子里

双非能在秋招上岸吗？牛客创作赏金赛

点赞评论收藏

10-18 13:01

已编辑

西安理工大学 C++

简历已经无敌了 你们肯定没办法找到问题

小米内推大使：建议技能还是放上面吧，hr和技术面试官第一眼想看的应该是技能点和他们岗位是否匹配

点赞评论收藏

11-18 16:08

福州大学 Java

扣税比我总包都高一大截

大佬们太狠了

影流之主：干10年不被裁，我就能拿别人一年的钱了，日子有盼头了

点赞评论收藏

11-22 19:10

大连理工大学产品助理

不太能适应大公司怎么办

办公室很大 人特别多 一层都是感觉跟工厂的流水线工人一样 每个人都是各干各的事情 有点适应不了每天上班都好煎熬呀 我目前还没有过试用期 纠结要不要换个

点赞评论收藏

点赞收藏评论

全站热榜

正在热议

# 25届秋招总结 #

272998次浏览 2317人参与

# 如果实习可以转正，你会不会放弃秋招 #

# 选完offer后，你后悔学本专业吗 #

# 你觉得专业和学校哪个对薪资影响最大 #

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

题意

算法（）

全站热榜

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