https://nanti.jisuanke.com/t/41355
思路
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define ft first
#define se second
#define pii pair<int,int>
#define db double
#define ls o<<1
#define rs o<<1|1
#define lowbit(x) (x&-x)
using namespace std;
const int M=2e6+5,T=1e6;
const ll P=998244353;
int x[2][2]={{1,0},{0,0}};
int y[2][2]={{3,1},{2,0}};
int z[2][2]={{1,0},{0,1}};
ll q,n;
struct mat{
ll d[2][2];
void init(int c[2][2]){
for(int i=0;i<2;i++)for(int j=0;j<2;j++)d[i][j]=c[i][j];
}
mat operator *(const mat& rhp)const{
mat tmp;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
tmp.d[i][j]=0;
for(int k=0;k<2;k++)
tmp.d[i][j]=(tmp.d[i][j]+d[i][k]*rhp.d[k][j]%P)%P;
}
}
return tmp;
}
}A[3][M];
void init(){
A[0][0].init(z);
A[0][1].init(y);
for(int i=2;i<=T;i++){
A[0][i]=A[0][i-1]*A[0][1];
}
A[1][0].init(z);
A[1][1]=A[0][T];
for(int i=2;i<=T;i++){
A[1][i]=A[1][i-1]*A[1][1];
}
A[2][0].init(z);
A[2][1]=A[1][T];
for(int i=2;i<=2*T;i++){
A[2][i]=A[2][i-1]*A[2][1];
}
}
ll gao(ll n){
if(n==0)
return 0;
if(n==1)
return 1;
mat B;
B.init(z);
for(int i=0;i<3&&n;i++){
int k=n%T;
if(i==2)k=n; //没有前导0
B=B*A[i][k];
n/=T;
}
return B.d[0][1];
}
int main(){
cin>>q>>n;
init();
ll res=0,f;
while(q--){
f=gao(n);
n^=f*f;
res^=f;
}
cout<<res<<endl;
return 0;
}