构造矩阵，递推n个硬币往前挪一个和挪两个的次数，容易发现是相互关联的递推式，就矩阵光速幂做完了。

递推式写成矩阵乘法形式如下：

$$[f_{i -1,1},f_{i - 1,2},1] \times \begin{bmatrix} 0 & 1 & 0\\ 2 & 2 & 0\\ 1 & 2 & 1\\ \end{bmatrix} =[f_{i,1},f_{i,2},1]$$

$O(\sqrt[4]n+T)$，空间 $O(\sqrt[4] n)$

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;

char getc()
{
    constexpr static int SIZ = 1 << 16;
    static char buf[SIZ],*p1 = buf,*p2 = buf;
    if(p1 == p2) p2 = (p1 = buf) + fread(buf,1,SIZ,stdin);
    return *p1++;
}

ll read()
{
    ll x = 0;
    char c;
    for(c = getc();!isdigit(c);c = getc());
    for(;isdigit(c);c = getc())
        x = x * 10 + (c ^ '0');
    return x;
}

constexpr int W = 3,mod = 998244353;

struct martix
{
    uint dl[3][2];
    void set(bool flag)
    {
        memset(dl,0,sizeof dl);
        dl[0][0] = dl[1][1] = 1;
    }
};

martix operator *(martix x,martix y)
{
    return martix{{
        {
            ((ull)x.dl[0][0] * y.dl[0][0] + (ull)x.dl[0][1] * y.dl[1][0]) % mod,
            ((ull)x.dl[0][0] * y.dl[0][1] + (ull)x.dl[0][1] * y.dl[1][1]) % mod
        },
        {
            ((ull)x.dl[1][0] * y.dl[0][0] + (ull)x.dl[1][1] * y.dl[1][0]) % mod,
            ((ull)x.dl[1][0] * y.dl[0][1] + (ull)x.dl[1][1] * y.dl[1][1]) % mod
        },
        {
            ((ull)x.dl[2][0] * y.dl[0][0] + (ull)x.dl[2][1] * y.dl[1][0] + y.dl[2][0]) % mod,
            ((ull)x.dl[2][0] * y.dl[0][1] + (ull)x.dl[2][1] * y.dl[1][1] + y.dl[2][1]) % mod
        }
    }};
}

struct Vector
{
    uint xl[2];
};

Vector operator *(Vector x,martix y)
{
    return Vector{{
        ((ull)x.xl[0] * y.dl[0][0] + (ull)x.xl[1] * y.dl[1][0] + y.dl[2][0]) % mod,
        ((ull)x.xl[0] * y.dl[0][1] + (ull)x.xl[1] * y.dl[1][1] + y.dl[2][1]) % mod
    }};
}

constexpr int N = 1015;
constexpr martix w{{{0,1},{2,2},{1,2}}};
martix dl[4][N];

int main()
{
    freopen("coin.in","r",stdin);
    freopen("coin.out","w",stdout);
    for(int i = 0;i < 4;i++)
    {
        dl[i][0].set(true);
        if(i == 0) dl[i][1] = w;
        else dl[i][1] = dl[i - 1][1000];
        for(int j = 2;j < N;j++)
            dl[i][j] = dl[i][j - 1] * dl[i][1];
    }
    // cerr << clock() << endl;
    int T;
    T = read();
    // scanf("%d",&T);
    ll a = 0,b = 0;
    while(T--)
    {
        ll n;
        n = read();
        // scanf("%lld",&n);
        Vector tmp = Vector{{dl[0][n % 1000].dl[2][0],dl[0][n % 1000].dl[2][1]}} * \
            dl[1][n % 1000000 / 1000] * dl[2][n % 1000000000 / 1000000] * dl[3][n / 1000000000];
        a ^= tmp.xl[0],b ^= tmp.xl[1];
    }
    printf("%lld %lld\n",a,b);
    // cerr << clock() << endl;
    return 0;
}

OEIS A005665 & A005666

好像是矩阵光速幂，就完了。