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 14:05

门头沟学院嵌入式软件开发

我们一直都是如履薄冰

oppo 应用软开 22*15+0.5*12

拿到了ssp完美：真的坎坷，但是你至少拿到这么多offer了！

点赞评论收藏

分享

11-24 15:00

Columbia University Java

bg：水硕，一段大厂一段中厂实习碎碎念：秋招一直处于半摆烂的状态，本来都打算回国直接当团小子了，结果最后开奖开了个挺低的包，感觉有点侮辱人，就重新捡起了好几个月没看的八股和算法重新开始投，但确实有点晚了所以基本也没面上几家。每天熬到凌晨三四点面试，早上六七点爬起来笔试，虽然好几家都走到了最后的hr面，但搞了这么久也就拿了个阿里云边缘部门的小sp，属实有点不甘心。不过幸运的是，朋友帮我找人推了个北美tt的开发岗，之前我自己投都是做完笔试就直接没消息了，没想到这次内推了下还真被捞起来进面了，三轮技术面+一轮hr面也都比较顺利，不得不感叹找工真的是9分看运气1分看实力（这里真得吐槽下sb淘天...

安多纳德：恭喜老哥这是以后留在北美了吗

点赞评论收藏

分享

11-11 09:31

香港中文大学后端

“面试官出车祸了今天面试要取消了”

Hello_WordN：咱就是说，除了生命其他都是小事，希望面试官平安，希望各位平时也多注意安全

点赞评论收藏

分享

10-14 23:01

已编辑

中国地质大学（武汉） Java

完全找不到实习啊

怎么办啊，求大佬指点

CUG芝士圈：虽然是网上的项目，但最好还是包装一下，然后现在大部分公司都在忙校招，十月底、十一月初会好找一些。最后，boss才沟通100家，别焦虑，我去年暑假找第一段实习的时候沟通了500➕才有面试

，校友加油

点赞评论收藏

分享

11-27 21:12

已编辑

哈尔滨工业大学 Java

一个接口是可以继承多个接口的抽象类实现一个接口时，可以实现也可以不实现接口中的方法。interface可用的修饰符只有public解析CQRS架构模式解析TDD架构模式常用于微服务架构中的Sidecar设计模式构造方法中如果没有super语句，默认在构造方法的第一行会加一个super()语句在同一个构造方法中this(参数)语句和super(参数)语句都必须放在第一行，那么在同一个构造方法中this(参数)语句和super(参数)语句只能有一个在Java语言中 ```int m[]=new int[5]``` 用 ```m.length``` 表示数组的长度，数组被当作对象包含一个变量leng...

查看9道真题和解析

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

正在热议

# 拼多多求职进展汇总 #

237500次浏览 2039人参与

# 机械求职避坑tips #

23679次浏览 249人参与

# 阿里云管培生offer #

62717次浏览 1761人参与

# 25届秋招总结 #

411759次浏览 4130人参与

# 25届机械人为了秋招做了哪些准备？ #

26312次浏览 363人参与

# 地方国企笔面经互助 #

6996次浏览 17人参与

# 北方华创开奖 #

67129次浏览 553人参与

# ai智能作图 #

29279次浏览 352人参与

# 虾皮求职进展汇总 #

91946次浏览 751人参与

# 实习，投递多份简历没人回复怎么办 #

2441220次浏览 34746人参与

# 软件开发投递记录 #

1481853次浏览 23947人参与

# 我的实习求职记录 #

6134632次浏览 84021人参与

# 我在牛爱网找对象 #

74905次浏览 555人参与

# 发工资后，你做的第一件事是什么 #

9211次浏览 43人参与

# 985本硕1个中小厂offer，摆烂or继续努力 #

83333次浏览 602人参与

# 机械人怎么评价今年的华为 #

157996次浏览 1352人参与

# 京东求职进展汇总 #

513185次浏览 4681人参与

# 如果可以，你希望哪个公司来捞你 #

34029次浏览 196人参与

# 你觉得通信/硬件有必要实习吗？ #

54806次浏览 698人参与

# 歌尔求职进展汇总 #

42919次浏览 294人参与

# 在职场上，你最讨厌什么样的同事 #

6110次浏览 91人参与

# 如果再来一次，你还会选择这个工作吗？ #

116048次浏览 1145人参与

牛客网
牛客企业服务