三校集训Part1 QZEZ Day2 A洗牌 题解

题意

无聊的时间,小$ K $喜欢和他的室友们一起打扑克(这副扑克很神奇,上面写着$ 1 $到$ n $的数字各一张),打扑克前当然要先洗牌啦。
宿舍洗牌的方式十分简单,先将所有牌平均分成两份,然后交叉地混合到一起,举个例子,六张牌$ 1$ $ 2$ $3$ $ 4 $ $5 $ $6$ 在混合后后会变成 $1$ $4$ $2$ $5 $ $ 3$ $6$,但是这样的问题很明显,第一张牌和最后一张牌一定不会变化,所以他们还要将最后的$ k $张牌移动到最前面,如此的过程,混合加上切牌,称为一次洗牌。
小$ Y $并不信任小$ K $的洗牌姿势,他决定让小$ K $进行若干次洗牌后,检查其中某些牌牌面的数字,来确定小$ K $是否手上抹油,他知道这样洗牌的结果是固定的,但却不知道应该是什么,你能帮帮他吗?

思路

抹油是什么意思?QWQ
转入正题,首先一看这数据范围就是$O(N$ $logN)$的复杂度,设这个变换函数为$f(x)$,然后第一次变换后就是$f(x)$,两次是$f(f(x))$,三次是$f(f(f(x)))$,以此类推$\dots$。
所以这个函数$f(x)$支持倍增。
那么就预先处理出$2^n$变换的$f$函数,对于每次询问倍增就好了。
设$f[i][j]$为$2^i$次,第$j$位的变换。
那么:$f[i][j]=f[i-1][f[i-1][j]];$
但是毒瘤出题人卡了倍增,但卡卡常也就过了。

Code

暂无评论

发送评论


				
上一篇
下一篇