这题题解是请教了学长之后才做出来的, 若是想看题解请看http://t.csdn.cn/unAyg
本篇文章只作为做题记录
写了一天半...感觉自己是不太适合写区域赛的题了, 还是多学学算法和数论好了
-----------------------------------------------------------------------------------------------------------------------
自己推了一个小时之后就不耐烦看题解了
最后看学长题解, 自己一开始推了一半的结论其实是没错的...错在我没有坚持下来就看了题解
做法2没看懂, 所以使用了做法1的公式
我的思路是这样的, 分别记录操作1和操作2的 前缀和 和 前缀和之和 直接取最大值然后套公式输出, 错误代码示范
写了半天跑出来的结果是这样的
跑去问队友lk, 他说把前面取模去掉了变成wa4, 很神奇, 然后我就疯狂的试取模, 发现了这一句
也就是说, 答案取模之后就不一定是最大值了! 改了半天结果还是
实在做的难受, 跑去问了学长, 学长好心写了篇题解, 一瞬间疑云消散...明白了做法1和做法2的真正意义...
假设操作1为A, 操作2为B
那么一共会有
AAA...A
AAA...B
AA...BB
..
BBB...B
m种序列
而真正意义上的最大, 是A和B操作各取一半 或 全取A的情况
做法1是计算了全部序列, 枚举B从哪里开始取, 取最大值 Om
做法2推出了 A和B操作各取一半 或 全取A的情况 这个结论 O1
---------------------------------------------------------------------------------------------------------------------------------
终于把这题ac了, 感觉学到了许多, 但确实目前阶段刷区域赛的题对于我来说还是太难了, 让我多学点算法明年战区域赛!
途中还了解了个费马小定理(还不能说会), 2的n次幂*ksm(2,mod-2)相当于2的n-1次幂