首页 > 其他 > 详细

CF1227F2 Wrong Answer on test 233 (Hard Version)

时间:2020-02-10 15:10:24      阅读:74      评论:0      收藏:0      [点我收藏+]

题意

\(n\)道题,每道题有\(k\)种选项,其中第\(i\)道题正确答案是\(a_i\),但是填答案的时候填错啦,第一道题的选择填到了第二道题...第\(n\)道题的选择填到了第一道题,求在\(k^n\)种方案中有多少种是填错比原来的方式正确数还要多的

做法

\(f_{i,j}\)为填前\(i\)道题,差为\(j\)的方案数,分类讨论相邻暴力转移\(O(n^2)\)

我们发现更优解跟更劣的方案数相同,即求\(\frac{k^n-f(n,0)}{2}\),然后随便搞搞就好了

CF1227F2 Wrong Answer on test 233 (Hard Version)

原文:https://www.cnblogs.com/Grice/p/12290815.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!