题目分析

本题通过矩阵快速幂的方法解决递推问题，具体是利用矩阵乘法和快速幂优化计算，以处理较大的输入规模。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
const LL P=1e9+7;
struct node
{
    LL a[4][4];
    node(){memset(a,0,sizeof a);}
};
LL n;
node operator*(node A,node B)
{
    node C; 
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            for (int k=1;k<=3;k++)
                C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P;
    for (int i=1;i<=3;i++)for (int j=1;j<=3;j++)C.a[i][j]=(C.a[i][j]%P+P)%P;
    return C;
}
node qpow(node A,LL b)
{
    node C;for(int i=1;i<=3;i++)C.a[i][i]=1;
    for(;b;b>>=1)
    {
        if(b&1)C=C*A; 
        A=A*A;
    }
    return C;
}
int main()
{
    int T;scanf("%d",&T);
    node A;
    A.a[1][1]=1;A.a[1][2]=2;A.a[1][3]=6;
    node ff;
    for(int i=2;i<=3;i++)ff.a[i][i-1]=1;
    ff.a[1][3]=-1;
	ff.a[2][3]=2;
	ff.a[3][3]=2;
    LL ans=0;
    for(int i=1;i<=T;i++)
    {
        //n^=n<<13;n^=n>>17;n^=n<<5;
        scanf("%lld",&n);
        node tno=A*qpow(ff,n-1);
        ans=ans^tno.a[1][1];
        //printf("%d:%lld\n",i,tno.a[1][1]);
    }
    printf("%lld\n",ans);
    return 0;
}

代码说明

1. 矩阵定义：定义node结构体表示3x3矩阵，用于存储递推关系的转移矩阵和初始向量。
2. 矩阵乘法：重载*运算符实现矩阵乘法，注意模运算和符号处理，确保结果非负。
3. 快速幂：qpow函数通过二分法实现矩阵快速幂，优化指数运算效率。
4. 主逻辑：
   • 读取测试用例数T，初始化初始矩阵A和转移矩阵ff。
   • 对每个测试用例，读取n，计算A * ff^(n-1)，提取结果并异或累加，最终输出结果。

通过矩阵快速幂，将线性递推的时间复杂度从O(n)优化至O(log n)，适用于处理大n的输入。