已知 $x$，将 $x \gets (x \oplus a) + b$ 执行 $t$ 次， $t$ 可能很大。求最后 $x$ 的值。

问一下大家有什么思路。

（以下内容写得很复杂，可以不看。）

我的想法是做操作 $x \gets (x \oplus a) + b) \oplus a$，再做 $x \gets x + b$。前者相当于 $b$ 中为 $1$ 的二进制位，在 $x$ 的对应位被加时，为 $0$ 则进 $1$ 并变为 $1$，为 $1$ 则变为 $0$。

然后解决 $b = 2^n$ 的情况，并推广到一般。用一下程序对 $x=0, a=3,5,7,9,11,13, b=64,t\le1000$ 作图如下：

#include<bits/stdc++.h>
using namespace std;
int x,a,b,t;
int main(){
	cin>>x>>a>>b>>t;
	while(t--){
		x=((x^a)+b)^a;
		cout<<x<<endl;
		x+=b;
		cout<<x<<endl;
	}
	return 0;
}

可以发现折线呈锯齿状。具体说，把每一项减去 $at$ 得：

但是 $a$ 很大时锯齿也会很复杂，求出它的复杂度较大。