2019-12-20 16:54 已编辑杭州电子科技大学研发工程师

关注

Educational Codeforces Round 78 (Rated for Div. 2)

前言

挺好一开局，要是D没被卡能把E也写了说不定还能上橙，可惜。

题解

F - Cards

题目要求 $\frac{\sum_{i=1}^nC_n^i*i^k*(m-1)^{n-i}}{m^n}$ 把分母拿掉，只考虑分子。
根据第二类斯特林数的性质有 $n^k=\sum_{i=0}^{n}C_n^i*S(k,i)*i!\\$
代入上式得 $\sum_{i=1}^n C_n^i*(m-1)^{n-i} \sum_{j=0}^{\min(i,k)} C_i^j*S(k,j)*j!\\$
交换求和得 $\sum_{j=0}^{min(n,k)}\sum_{i=j}^n C_n^i*C_i^j*(m-1)^{n-i}*S(k,j)*j!\\$
把组合数拆开得 $\sum_{j=0}^{min(n,k)}\sum_{i=j}^n \frac{n!}{(n-i)!*i!}*\frac{i!}{(i-j)!*j!}*(m-1)^{n-i}*S(k,j)*j!\\$
化简得 $\sum_{j=0}^{min(n,k)}S(k,j)\sum_{i=j}^n \frac{n!}{(n-i)!*(i-j)!}*(m-1)^{n-i}\\$
再给后面的组合数乘点东西 $\sum_{j=0}^{min(n,k)}S(k,j)\sum_{i=j}^n \frac{n!}{(n-j)!}*\frac{(n-j)!}{(n-i)!*(i-j)!}*(m-1)^{n-i}\\$
于是就变成了 $\sum_{j=0}^{min(n,k)}S(k,j)\frac{n!}{(n-j)!}\sum_{i=j}^n C_{n-j}^{i-j}*(m-1)^{n-i}\\$
用 $i$ 替换 $i-j$ ，得到 $\sum_{j=0}^{min(n,k)}S(k,j)\frac{n!}{(n-j)!}\sum_{i=0}^{n-j} C_{n-j}^{i}*(m-1)^{n-j-i}\\$
最终的式子为 $\sum_{j=0}^{min(n,k)}S(k,j)*\frac{n!}{(n-j)!}*m^{n-j}\\$
第二类斯特林数 $O(k^2)$ 预处理, $O(k)$ 求解。

全部评论

推荐最新楼层

11-29 18:15

已编辑

字节跳动_前端开发(实习员工)

秋招结束，历经9个月的总结

bg：9 本科班，2 段实习（1 段对口），暑期 3 offer（2 大 1 中），秋招 4 offer（4 大）。最后一个 offer 回复时间静悄悄地超时了。那一刻，其实没有什么戏剧性的情绪，就是电脑右下角的时间又跳了一分钟，我突然意识到：从 2 月份开始折腾的这一整段——找实习、实习、秋招——算是正式收官了。如果把时间轴再拉长一点，这大概也是我过去 21 年里，最重要的几个节点之一。一、从 2 月到 8 月：实习把我推上了牌桌2 月开始找实习，一路面到 4、5 月，前前后后加起来 30+ 轮面试。当时的心路历程我在牛客上写过一篇长篇流水账：https://www.nowcoder.com...

牛客51700980...：蜀黍不去备战major搁这找工作？想再一次坐地牢里吃法棍了是吧

2025年终总结

点赞评论收藏

分享

不愿透露姓名的神秘牛友

11-28 21:27

半导体fab or 🌸为

bg双9但是没有实习现在比较中意的offer要么回家（二线城市）要么去上海1、半导体fab厂：n*14，it岗，做cim系统（在招聘软件上粗略看了下能跳一些制造业的it岗），不倒班2、🌸为：n*(14-16)，通软，做鸿蒙系统但不是鸿蒙开发（不太了解如果跳槽能跳到哪里），加班猛其中fab厂的n是月基本工资，🌸为的n中包含绩效。另外这两家公司都额外有加班费主要纠结的点是fab厂离家近薪资在当地高，但是平台和风评较差；🌸为平台大，但是在上海这薪资有点低了（总包不到35，感觉是13a）另外也想了解一下两种职业未来个人发展方向（比如能跳槽到哪里去，哪个职业更好跳槽，抛开公司哪个职业未来更稳定一些...

点赞评论收藏

分享

11-18 17:58

南昌大学辅导教师

家人们，这种简历是不是注定找不到工作😭，银行四大行全挂了，城市商业银行过了两个，但是一面全挂了，现在想找实习也找不到，真不知道能做啥工作了，能给给意见嘛

金融银行求职进展汇总

点赞评论收藏

分享

10-27 02:29

已编辑

门头沟学院嵌入式工程师

双非本科0offer。

秋招面了四家，结果四家全跪。笔试，技术面都过了，结果hr面听我四级没过直接给我拒了。做嵌入式英语四级没过影响真的这么大吗😭

牛客72783561...：简历不是这么写的，你这两个项目只说了用到了什么技术，却没说取得了什么成果，在我看来这就是你自己做的一个demo，没有价值。你为什么不写你电赛国二的那个项目？

点赞评论收藏

分享

昨天 09:36

复旦大学 Java

Redis刷题题库

1.Redis为什么快？ 基于内存操作：Redis的绝大部分操作在内存里就可以实现，数据也存在内存中，与传统的磁盘文件操作相比减少了IO，提高了操作的速度。高效的数据结构：Redis有专门设计了STRING、LIST、HASH等高效的数据结构，依赖各种数据结构提升了读写的效率。采用单线程：单线程操作省去了上下文切换带来的开销和CPU的消耗，同时不存在资源竞争，避免了死锁现象的发生。I/O多路复用：采用I/O多路复用机制同时监听多个Socket，根据Socket上的事件来选择对应的事件处理器进行处理。2.为什么Redis是单线程？单线程指的是：网络请求模块使用单线程进行处理，其他模块仍用多个线程...

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

更多

华为开奖交流

热聊中

创作者周榜

更多

正在热议

更多

# 为了去实习，我赌上了___ #

14876次浏览 159人参与

# 晒一晒你收到的礼盒 #

87482次浏览 426人参与

# uu们，春招你还来吗？ #

7202次浏览 58人参与

# 2025年终总结 #

7350次浏览 140人参与

# 十二月请对我好一点 #

20446次浏览 288人参与

# 降低公积金和取消房补怎么选 #

22948次浏览 75人参与

# 父母对你找工作是助力还是阻力？ #

10228次浏览 172人参与

# 实习打杂，要跑路吗 #

50481次浏览 320人参与

# 第一份工作能做外包吗？ #

84731次浏览 568人参与

# 电信求职进展汇总 #

31081次浏览 166人参与

# 学历or实习经历，哪个更重要 #

200828次浏览 1059人参与

# 哪一瞬间让你觉得“这班不如不上” #

7739次浏览 117人参与

# 一人推荐一个值得做的项目 #

7123次浏览 102人参与

# 高薪高压 vs 低薪wlb，你怎么选？ #

7866次浏览 89人参与

# 工作前VS工作后，你的心态变化 #

10126次浏览 133人参与

# 找工作时的取与舍 #

110179次浏览 828人参与

# 工作中出现了XX情况正常吗 #

25502次浏览 196人参与

# 市场营销人求职交流聚集地 #

162639次浏览 1212人参与

# 公司福利里最没用的一项是啥 #

5320次浏览 86人参与

# 回顾今年你干过的最“勇”的一件事 #

10592次浏览 139人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务