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)$ 求解。

全部评论

推荐最新楼层

02-28 22:37

中南大学 Java

除了java，还有哪个行业能这么令人难绷？

都说“既让驴拉磨，又不让驴吃饱”，俺寻思就是真驴一天10块也不一定能吃饱吧，什么人形核动力驴，还是性价比太高了。想要学习Java冲实习或冲春招的，我能助你一臂之力，我之前整理了高质量可速成的魔改外卖项目话术和轮子项目话术，还有超全超精品八股大全专栏（超千人订阅，牛客最受欢迎最高质量java八股专栏），怎么写简历，怎么包装实习经历，怎么0基础速成冲春招和实习等等等等精品帖子，大家可以去看看：https://www.nowcoder.com/discuss/721704696242536448?sourceSSR=users我的八股大全专栏（内有魔改苍穹外卖话术）：https://www.nowc...

Jsann：方便面3块1袋一天三袋哪里吃不饱了

牛客创作赏金赛

点赞评论收藏

分享

02-28 16:56

山东财经大学产品经理

【华为OD面经】双非本零实习上岸实录

📅 时间线3.15 简历投递3.20 机考（395/600）3.25 技术一面（75min）3.28 技术二面（90min）4.2 主管面（45min）4.5 Offer call💻 机考真题复盘（Java方向）第一题：字符串压缩协议 题目：实现华为设备间通信的字符串压缩算法 输入示例：AAAABBBCCDAA 输出示例：4A3B2C1D2A 考察点：字符串遍历+边界处理（AC代码见评论区） 第二题：服务节点熔断策略 场景：分布式系统中有N个节点，给定故障概率数组，求保证系统可用性的最小监控节点数 输入示例：[0.2, 0.3, 0.1] 输出示例：2 解题思路...

查看11道真题和解析华为工作体验

点赞评论收藏

分享

01-15 10:19

中华女子学院 Java

福报又又又来了

已经打算旷工处理了。#中关村科金

kl_我是东山啊：《相关公司：阿里巴巴》

投递阿里巴巴等公司10个岗位

点赞评论收藏

分享

今天 09:10

博云_AIOS产品技术部_云原生AI实习工程师(实习员工)

腾讯 - 软件开发-后台开发方向 - 腾讯安全 - 一面

#腾讯# #面经#全长：1小时15分钟全程项目细节追问一点八股都没有，挑点有意思的写写项目并发量/用户使用量增多了，需要做什么数据库操作适应？项目的接口安全性校验有做过吗？如果要做数据库的同步，怎么做会比较好？有了解过Mysql中的修改操作的底层逻辑吗？(答Cache落盘那些东西)事务在你的项目中不会导致并发性问题吗？为什么要用事务？Golang中的特性比如协程通信什么的讲一下？(问设计思想)Golang中的GC有了解过吗？(问底层)看到你的项目中有Golang调C的库进行交互，他们之间的通讯形式是什么？(问底层)Golang和C的交互那块它们的内存释放需要你去手动释放还是Golang的GC做...

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

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 腾讯求职进展汇总 #

370391次浏览 3014人参与

# 面试常问题系列 #

8267次浏览 265人参与

# 神州信息求职汇总 #

40607次浏览 286人参与

# 职场中你干过哪些“蠢”事 #

89669次浏览 473人参与

# 2025退税开始啦 #

13625次浏览 232人参与

# 面试时被问的最奇葩的问题 #

14965次浏览 88人参与

# 面试被问期望薪资时该如何回答 #

205600次浏览 1246人参与

# 我在牛爱网找对象 #

155159次浏览 1187人参与

# 传音控股求职进展汇总 #

5707次浏览 35人参与

# 双非本科的出路是什么？ #

105668次浏览 1030人参与

# 非技术岗投递进展 #

116901次浏览 975人参与

# 通信/硬件求职避坑tips #

39808次浏览 328人参与

# 职场新人生存指南 #

236195次浏览 5983人参与

# 如何排解工作中的焦虑 #

121581次浏览 1515人参与

# 那些我实习了才知道的事 #

164565次浏览 1391人参与

# 运营每日一题 #

54679次浏览 507人参与

# 如果有时光机，你最想去到哪个年纪？ #

37616次浏览 705人参与

# 汇川技术求职进展汇总 #

106366次浏览 736人参与

# 招银网络求职进展汇总 #

93754次浏览 601人参与

# 安克创新求职进展汇总 #

18340次浏览 144人参与

# 你觉得机械有必要实习吗 #

36366次浏览 345人参与

牛客网
牛客企业服务