思路：矩阵快速幂+map
代码：
#include<cmath> #include<algorithm> #include<cstdio> #include<map> const int INF=0x3f3f3f3f; const int maxn = 1e7+10; const int mod=998244353; using namespace std; typedef long long ll; map<ll,ll> mp; ll n; struct mat { ll m[4][4]; }unit; mat operator * (const mat &a,const mat& b) { mat q; q.m[1][1] = (a.m[1][1]*b.m[1][1] + a.m[1][2]*b.m[2][1])%mod; q.m[1][2] = (a.m[1][1]*b.m[1][2] + a.m[1][2]*b.m[2][2])%mod; q.m[2][1] = (a.m[2][1]*b.m[1][1] + a.m[2][2]*b.m[2][1])%mod; q.m[2][2] = (a.m[2][1]*b.m[1][2] + a.m[2][2]*b.m[2][2])%mod; return q; } mat f,ans; ll pow_mat(mat a,ll n) { if(mp.count(n)) return mp[n]; ll temp = n; while(n) { if(n&1) { n--; f=f*a; } n>>=1; a=a*a; } return mp[temp] = f.m[1][1]%mod; } ll kk[maxn]; int main() { ll Q,N; scanf("%lld%lld",&Q,&N); ll tmp=N; for(int i=0; i<Q; i++) { f.m[1][1]=1; f.m[1][2]=0; ans.m[1][1]=3; ans.m[1][2]=1; ans.m[2][1]=2; ans.m[2][2]=0; ll nn= pow_mat(ans,tmp-1); kk[i] = nn % mod ; tmp^=(nn*nn); } ll aa=kk[0]; for(int i=1; i<Q; i++) { aa^=kk[i]; } printf("%lld ",aa%mod); return 0; }