思路：

先用特征根法求出通向公式，然后通向公式中出现了\(\sqrt{17}\)，这个可以用二次剩余求出来，然后可以O(\(log(n)\))求出。

但是还不够，我们先对\(n\)欧拉降幂，然后求base为\(\sqrt{1e9}\)的快速幂，预处理一些东西，就可以类似O(1)求出了。

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int MOD = 998244353;const LL fsqrt17 = 473844410;const LL sqrt17 = MOD-fsqrt17;const LL inv2 = (MOD+1)/2;const LL invsqrt17 = 438914993;const int N = 4e4 + 5;LL p[N], pp[N], P[N], PP[N], q, n;LL f(LL n) { return (p[n%(N-1)]*P[n/(N-1)])%MOD;}LL F(LL n) { return (pp[n%(N-1)]*PP[n/(N-1)])%MOD;}int main() { p[0] = pp[0] = 1; for (int i = 1; i < N; ++i) p[i] = p[i-1]*(3+sqrt17)%MOD*inv2%MOD, pp[i] = pp[i-1]*(3+fsqrt17)%MOD*inv2%MOD; P[0] = PP[0] = 1; for (int i = 1; i < N; ++i) { P[i] = P[i-1]*p[N-1]%MOD; PP[i] = PP[i-1]*pp[N-1]%MOD; } scanf("%lld %lld", &q, &n); LL res = 0; for (int i = 1; i <= q; ++i) { LL ans = -(f(n%(MOD-1))-F(n%(MOD-1)))*invsqrt17%MOD; ans = (ans + MOD) % MOD; res ^= ans; n ^= ans*ans; } printf("%lld\n", res); return 0;}