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-26 18:05

中国人民大学 Unity3D客户端

一直以为同事是针对我

之前有个不太熟的同事，我每次见到他他都一张臭脸，一开始我以为我们磁场不合，他可能有点针对我，最近以为装修换了工位才发现，原来是一视同仁的对每个人臭脸，是我错怪他了😭

点赞评论收藏

分享

11-27 19:55

已编辑

门头沟学院前端工程师

三方已签，秋招结束，我的碎碎念

自收到三方签订的邮件那一刻起，我的秋招正式结束了。虽然九月底就结束了最后一面，但是后面的泡池子、等开奖也等的心力憔悴。直到这一刻，感觉一切落定，未来暂不知是否光明，但是我对它充满期待。这是我对秋招的最后一个总结帖了。相比起上一次阶段性小结，基本都知道最终的结果了（除了京东还在泡）总共拿了6个意向/oc：1.字节-抖音（已签）2.美团-到家（已拒）3.百度-能力平台（已拒）4.滴滴-用户增长（已拒）5.快手-用户增长（保温）6.顺丰-顺丰科技（已拒）感慨一下今年的薪资今年最让我感到惊讶的一点是薪资。一开始我和身边的同学都对团子不报期待，想着用它保底，开水团的名号没少听，往年的薪资也确实不尽人意，...

别看我了哥们：Xy✌🏻还需要攒结婚奶粉钱，我这种***丝该咋办

上班苦还是上学苦呢？如果可以选，你最想去哪家公司

点赞评论收藏

分享

11-14 08:35

河北地质大学华信学院网络工程师

大佬们帮忙看一下我的简历有问题吗

菜菜咪：1. 可以使用简历网站的模版，美观度会更好一点 2. 邮箱可以重新申请一个，或者用qq邮箱的别名，部分hr可能会不喜欢数字邮箱 3. 项目经历最好分点描述，类似的项目很多，可以参考一下别人怎么写的 4. 自我评价可加可不加，技术岗更看重技术。最后，加油，优秀士兵

点赞评论收藏

分享

11-29 00:18

门头沟学院 C++

对于Cpp选手

对于Cpp选手，基本都是背完八股，复盘完项目实习然后就开始秋招了秋招能找到啥工作然后就在其中选一个自己比较想去的感觉Cpp实际上并不太能说出一个具体方向，而是看自己秋招能找到什么方向的工作，而每个方向上其实差别还是非常大的，通常会涉及到不同的技术，最典型的代表就是学的后端，面试面的客户端，或者嵌入式

秋招相关文章牛客创作赏金赛如果再来一次，你还会选择这个工作吗？

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

正在热议

# 拼多多求职进展汇总 #

237656次浏览 2040人参与

# 机械求职避坑tips #

23710次浏览 249人参与

# 北方华创开奖 #

67173次浏览 553人参与

# 25届秋招总结 #

412592次浏览 4146人参与

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

26339次浏览 363人参与

# 地方国企笔面经互助 #

7032次浏览 17人参与

# 阿里云管培生offer #

62949次浏览 1762人参与

# ai智能作图 #

29526次浏览 353人参与

# 虾皮求职进展汇总 #

92548次浏览 758人参与

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

2441496次浏览 34746人参与

# 软件开发投递记录 #

1482007次浏览 23949人参与

# 我的实习求职记录 #

6135329次浏览 84024人参与

# 我在牛爱网找对象 #

74914次浏览 555人参与

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

9317次浏览 43人参与

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

83409次浏览 602人参与

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

158025次浏览 1352人参与

# 京东求职进展汇总 #

513298次浏览 4681人参与

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

34096次浏览 196人参与

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

54821次浏览 698人参与

# 歌尔求职进展汇总 #

42924次浏览 294人参与

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

6136次浏览 92人参与

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

116278次浏览 1145人参与

牛客网
牛客企业服务