隐藏
【51nod算法马拉松19 D】剪刀石头布威力加强版


【51nod算法马拉松19 D】剪刀石头布威力加强版

 

写在前面

这题是坑啊!窝就因为读优写炸了然后调了一上午(果然YPC是只蒟蒻)……

 

思路瞎JB乱搞

在某一天,正当我收拾收拾打算回家的时候,突然,大佬推荐我做这道数论水题,于是我就愉快的入了坑……

但是思考了分钟后,我就发现了:窝实在不会啊!所以窝去找了大佬问了这道题目……

又想起了佳龙学长的对我的谆谆教诲:这种东西找循环就好了!(窝:窝不会找啊)……嗯?不会找循环?做不来?(窝:找到了循环还是真的很难做啊……)那你学什么信竞?(窝:T_T)。

回忆了一下以前,所以现在不扯皮了。

这道题目其实还相当有难度的(要不是佳龙学长写过,不然我根本不会啊……)。

首先这道题目我们需要有个笨蛋的想法。

假设我们匹配,发现赢了,那么下次再匹配到了的时候,与之相匹配的就不一定是了(因为长度不相等啊),但是我们可以确定的是,跟下次跟匹配的一定是往后推了个单位的那个,那么我们就需要统计当前这个出法对于答案的贡献值。

问题来了:如何计算贡献值?

其实我也不会……

不难发现,其实由于数组位置会往后推,所以其实数组形成了若干个环。

如果一共有局。令表示这个出法赢了多少次,而且,那么显而易见(拖下去打):贡献值一定会有。对于剩下的再简单处理一下就好了,说的具体一点,就是如果把这个剩下来的环展开来,那么就会对应环上一个长度为的循环区间,这玩意儿我们可以用前缀和来做。

然后 暴力枚举就好了。

 

代码