2020-12-22 22:12 已编辑未填写教育信息 C++

关注

C题题解

挑选方案问题

https://ac.nowcoder.com/acm/contest/10322/C

机房同学让我看的题，然后随便推了一下就出来了，本质上是生成函数裸题

考虑五种限制

update:机房同学说有地方手残写错了见谅qaq，已更正

1：可以取无限个，对应的生成函数为 $\sum_{i=0}^{}x^i$

2：有一个，对应的生成函数为 $1+x$

3：有四个，对应的生成函数为 $1+x+x^2+x^3+x^4$

4：无限但只能取偶数个，对应的生成函数为 $\sum_{i=0}^{}x^{2i}$

5：无限但只能取 $5$ 的倍数个，对应的生成函数为 $\sum_{i=0}^{}x^{5i}$

分别写成封闭形式然后卷积可以得到为 $\frac{1}{1-x}\times \frac{1-x^2}{1-x}\times \frac{1-x^5}{1-x}\times \frac{1}{1-x^2}\times \frac{1}{1-x^5}=\frac{1}{(1-x)^3}$

然后由牛顿二项式定理可得对应的生成函数为 $\sum_{i=0}C_{n+2}^{n}x^n$

那么答案就为 $C_{n+2}^{n}=\frac{(n+1)\times (n+2)}{2}$ 代码就不贴了

全部评论

推荐最新楼层

北京交通大学机械工程师

太高深，听不懂，点赞

1 回复分享

发布于 2020-12-22 23:13

客户端劝退第四人

门头沟学院 C++

%%%%

点赞回复分享

发布于 2020-12-26 21:34

滴滴_mpt_后端工程师

应该是1/(1-x)^3吧

点赞回复分享

发布于 2020-12-22 22:08

滴滴_mpt_后端工程师

%%%

点赞回复分享

发布于 2020-12-22 21:54

努力求职不异地

重庆大学产品经理

%%%

点赞回复分享

发布于 2020-12-22 21:52

湖南科技学院 C++

%%%

点赞回复分享

发布于 2020-12-22 21:38

字节跳动_后端开发工程师

%%%

点赞回复分享

发布于 2020-12-22 21:28

John Bapst Memorial High School FPGA工程师

%%%

点赞回复分享

发布于 2020-12-22 21:17

腾讯_CDG_后端开发

%%%

点赞回复分享

发布于 2020-12-22 21:17

01-26 22:24

电子科技大学 Java

28届电科沙河人再次求助

大二Java后端那套学的还可以，写了一个点评，（苍穹外卖全是增删改查，学校搞综设的时候负责后端和部分深度学习的我那时候写过增删改查，git啥的都用过了，所以就没写）。现在在写leetcode和刷八股，八股侧重操作系统和计算机网络一点。因为其他的在学习项目中因为我这人比较喜欢刨根问底一点，所以底层的一些东西学的时候就理解了一下，现在主要是微服务还没系统学过，不想看微服务了系统的，再找个其他有含金量一点的项目看一下就准备投日常大厂实习了。 想问问各位佬，日常大厂实习在什么时候开投最合适，因为想在秋招前攒3~4段实习

点赞评论收藏

分享

01-15 07:26

吉首大学算法工程师

清华大学前端实习生

27届第一段实习，本来打算投投看没想到拿offer了。这种大学的实习是啥意思，和正常的互联网实习有啥区别。应该选哪个比较好。

哞客37422655...：老师自己开的那种接私活的吧

点赞评论收藏

分享

昨天 14:38

中原工学院嵌入式软件工程师

兄弟们给点建议，有点迷茫了，双非本科，进了个小厂嵌入式测试实习，但是想做开发，培训机构出来的，真心求点建议！

今年春招是金一银二嘛？

点赞评论收藏

分享

评论

20

5

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 今年春招是金一银二嘛？ #

16627次浏览 190人参与

# 总结:哪家公司面试体验感最好 #

78960次浏览 439人参与

# 赚钱的意义在这一刻具象化 #

8048次浏览 181人参与

# 来聊聊你目前的求职进展 #

717176次浏览 6982人参与

# 没关系，至少我的__很曼妙 #

7310次浏览 128人参与

# AI求职实录 #

9969次浏览 282人参与

# 抛开难度不谈，你最想去哪家公司？ #

9317次浏览 174人参与

# 为什么有人零实习也能进大厂？ #

9124次浏览 196人参与

# 1月小结：你过的开心吗？ #

3298次浏览 67人参与

# AI时代的工作 VS 传统时代的工作，有哪些不同？ #

11771次浏览 287人参与

# 你的第一家实习公司是什么档次？ #

7414次浏览 101人参与

# 快手年终开大包 #

2055次浏览 39人参与

# 当你问AI“你会取代我的工作吗”，它说_？ #

5973次浏览 180人参与

# 你的landing期是如何度过的？ #

12204次浏览 235人参与

# 牛客吐槽大会 #

6512次浏览 119人参与

# 除了Java，最推荐学什么技术？ #

9954次浏览 210人参与

# 你见过最离谱的招聘要求是什么？ #

255075次浏览 1730人参与

# 机械人你知道哪些单休企业 #

83513次浏览 417人参与

# 初创公司值得加入吗？ #

37479次浏览 217人参与

# 你觉得什么岗位会被AI替代 #

37509次浏览 256人参与

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