2019 南昌网络赛 H The Nth Item

#include <bits/stdc++.h>
#include <cstring>
#define ll long long
using namespace std;
const ll mod = 998244353;
const ll loop = 499122176;
struct Mat {
	int n,m;
	ll mem[2][2];
	Mat(int n, int m) {
		this->n = n, this->m = m;
		memset(mem, 0, sizeof mem);
		return;
	}
	Mat operator*(const Mat &a)const {
		Mat c(n,a.m);
		for (int i = 0; i < c.n; i++) {
			for (int j = 0; j < c.m; j++) {
				for (int k = 0; k < m; k++)
					c.mem[i][j] += mem[i][k] * a.mem[k][j];
				c.mem[i][j] %= mod;
			}
		}
		return c;
	}
};
Mat solve(Mat a,Mat c,char *s) {
	Mat b = c;

//	printf("%s\n",s);
	for(int i=strlen(s)-1; i>=0; i--) {
		int cur = s[i] - '0';
		while(cur--) b = b*a;
		Mat tmp = a*a;
		a = tmp*tmp;
		a = a*a*tmp;
	}
	return b;
}
ll num;
ll cf;
map<ll,ll> q;
char s[5000];
int main() {
	ll x0,x1,a,b;
	ll tmp,loop;
	Mat m1(2,2),m2(2,2);
	x0 = 0;
	x1 = 1;
	a = 3;
	b = 2;
	m1.mem[0][0] = 0;
	m1.mem[0][1] = b;
	m1.mem[1][0] = 1;
	m1.mem[1][1] = a;
	m2.mem[0][0] = x0;
	m2.mem[1][0] = 0;
	m2.mem[0][1] = x1;
	m2.mem[1][1] = 0;
	scanf("%lld",&num);
	scanf("%lld",&cf);

	ll f1,f2,f3,ans=0,last;

	for(int i=1; i<=num; i++) {
		//ltoa(cf,s,10);
		if(q[cf]==0) {
			sprintf(s,"%lld",(cf));
			m1.mem[0][0] = 0;
			m1.mem[0][1] = b;
			m1.mem[1][0] = 1;
			m1.mem[1][1] = a;
			m1 = solve(m1,m2,s);
			last = m1.mem[0][0];
			q[cf] = last;
			ans^=last;
			cf = cf^(last*last);
		} else if(q[cf]!=0) {
			last = q[cf];
			cf = cf^(q[last]*q[last]);
			ans^=last;
			continue;
		}
	}
	printf("%lld",ans);
	return 0;
}
/*
1 1 2 2
1 8
*/