遇到这道题可以先去看一道题，上帝与集合的正确用法
我们现在可以考虑这么一个问题
对于一个数字来说 它存活n秒之后剩下的序列多久可以把它清空
这个的话
记f为存活时间，易得
f0[n] = 1;
f1[n] = n+1
f2[n] = 3*2^n-n-2 （orz这个打表找规律吧，实在不想推
那么可以得到一个算法，直接对这个字符串扫一遍，不断记录当前时间，以及当前扫到的数字在活了当前时间的情况下需要多久删完。
然而你发现你需要处理这么一个问题
ai = 3*2^ai-1-ai-1-2
那么考虑我刚刚提到的那道题目其实你能发现这个题目可以转换为2^(xxxx^xxxx^xxxxx.....) 每一个2出现就是把前面的数字作为幂写上去
然后直接欧拉降幂
考虑1e9+7在大概28的时候降幂出来是1然后直接令now = 0就好了
然后预处理出1e9+7一路求phi的值
1000000007,1000000006,500000002,243900800,79872000,19660800,5242880,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1 然后统计当前数列有几个数字2，如果小于等于28的时候
if(s[i] == '0') now = (now+1)%phi[num];
if(s[i] == '1') now = (now+now+1)%phi[num];
if(s[i] == '2') {now = (now+3*power(2,now,phi[num-1])-(now+2)%phi[num-1]+phi[num-1])%phi[num-1]+phi[num-1];--num;}
全部评论
(0) 回帖