对于一个排列C={1, 2,3,....n},可以通过某一种方式打乱其顺序,设这种方式为P,也就是说C*P = C',C'为打乱后的顺序
如果打乱n次,得到的结果就是C*P^n,这是可以使用二进制的方法在log(n)的复杂度下计算出最后结果
我发现很多操作都可以使用二进制的方法快速计算,只要操作满足结合律即可
//计算p^tm,ret为结果
while(tm)
{
if(tm&1) op(ret, p);
op(p, p);
tm >>= 1;
}
对于一个排列C={1, 2,3,....n},可以通过某一种方式打乱其顺序,设这种方式为P,也就是说C*P = C',C'为打乱后的顺序
如果打乱n次,得到的结果就是C*P^n,这是可以使用二进制的方法在log(n)的复杂度下计算出最后结果
我发现很多操作都可以使用二进制的方法快速计算,只要操作满足结合律即可
//计算p^tm,ret为结果
while(tm)
{
if(tm&1) op(ret, p);
op(p, p);
tm >>= 1;
}