gym102501H Pseudo-Random Number Generator 循环节

(Updated: )
(2 mins to read)

给定一个数列的递推方式，求其前n项中偶数的个数$M=1ull<<40$$s0=0x600DCAFE$$s_{n+1} = (s_n + (s_n >> 20) + 12345)%M$$n \lt 2^{63}$

做法

因为要模M，所以猜想有循环节找循环节的方式是用链表的判环算法（快慢指针）快慢指针同时位于起点，然后快指针一次走两步，慢指针一次走一步，若两者相遇说明有环，此时让一个指针从起点开始，一个指针从相遇点开始，一次各走一步，当两者相遇，该点就是入环点以下代码返回入环点

1
2
3
4
5
6
7
8
9
10
11
12
13
ull findloop()
{
  ull fst = 0x600DCAFE, slw = 0x600DCAFE;
  while(true)
  {
    slw = nxt(slw);
    fst = nxt(nxt(fst));
    if(fst==slw) break;
  }
  slw = 0x600DCAFE;
  while(slw!=fst) slw = nxt(slw), fst = nxt(fst);
  return slw;
}

知道入环点后，让一个指针在起点走至该点的步数就是循环节开始的位置

1
2
3
4
5
6
ll f(ull x)
{
  ull s = 0x600DCAFE; ll len = 0;
  while(s!=x) len++, s = nxt(s);
  return len;
}

让一个指针从入环点下一个开始再走至入环点的步数+1就是循环节的长度（环长）

1
2
3
4
5
6
ll g(ull x)
{
  ull s = nxt(x); ll len = 1;
  while(s!=x) len++, s = nxt(s);
  return len;
}

得到的结果是st = 350125310, loop = 182129209这样还是过不了，我们可以利用分段打表，将前st项每隔1e6个数记录一下前缀答案，循环节也每隔1e6个数记录一下前缀答案，此外还要记录一下该点对应处的数列的取值。这样对于整块我们可以直接得到答案，而后面不完整的块再暴力一下即可。