牛客534819680号
2021-04-09 13:19 北京航空航天大学 算法工程师
关注
将串分成四类：
1. 没有3连 + 末尾两个数字不同， A[L]
2. 没有3连 + 末尾两个数字相同， B[L]
3. 恰有1个3连 + 末尾两个数字不同， C[L]
4. 恰有1个3连 + 末尾两个数字相同， D[L]
有如下递推关系：
A[2] = S * (S - 1)
B[2] = S
C[2] = 0
D[2] = 0
令R = S - 1以方便书写
A[L+1] = A[L] * R + B[L] * R
B[L+1] = A[L]
C[L+1] = C[L] * R + D[L] * R
D[L+1] = B[L] + C[L]
最后输出结果C[L] + D[L]之和即可。
时间复杂度为O(L)
查看原帖
点赞 评论
相关推荐
牛客热帖
正在热议
# 25届秋招总结 #
328264次浏览 3096人参与
# 上班苦还是上学苦呢？ #
72527次浏览 647人参与
# 百度开奖 #
183559次浏览 1148人参与
# 地方国企笔面经互助 #
4504次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
21702次浏览 401人参与
# 选完offer后，你后悔学本专业吗 #
21893次浏览 159人参与
# 阿里云管培生offer #
36994次浏览 422人参与
# 我的实习求职记录 #
6070365次浏览 83542人参与
# 如何一边实习一边秋招 #
996688次浏览 12664人参与
# 找工作时遇到的神仙HR #
553379次浏览 3801人参与
# 入职第一天，你准备什么时候下班 #
21625次浏览 144人参与
# 招聘要求与实际实习内容不符怎么办 #
10782次浏览 277人参与
# bilibili求职进展汇总 #
33217次浏览 357人参与
# 许愿池 #
214779次浏览 2534人参与
# 学历or实习经历，哪个更重要 #
53884次浏览 422人参与
# 你今年的平均薪资是多少？ #
70786次浏览 345人参与
# 实习工作，你找得还顺利吗？ #
247750次浏览 2907人参与
# 通信硬件薪资爆料 #
608878次浏览 5169人参与
# 海康威视求职进展汇总 #
400749次浏览 3408人参与
# 携程求职进展汇总 #
135738次浏览 931人参与
# 正在实习的你，几点下班 #
53349次浏览 396人参与
# 工作两年想退休了 #
53105次浏览 672人参与