Wannafly Winter Camp 2019 Day7 C 斐波那契数列 (矩阵快速幂)

https://zhixincode.com/contest/24/problem/C
题意：定义$Fi{b}_n$为斐波那契数列的第$n$项，现在给定$R$，求${\sum }_{n=1}^R(Fi{b}_n\&(Fi{b}_n?1))$ 。

这个题看上去和lowbit有关，因为对于一个数$x$，$x\&(x?1)=x?lowbit(x)$，所以题目转变为求$Fi{b}_n$的前$n$项和$lowbit(Fi{b}_n)$的前$n$项和然后作差。
斐波那契数列的前$n$项和$ans1$可以通过矩阵快速幂求得，此处不做详细说明。
$lowbit(Fi{b}_n)$的前$n$项和$ans2$就没法通过矩阵快速幂求得了，但通过打表找规律其实可以发现规律（下图为前100项$lowbit(Fi{b}_n)$的值）

循环周期为$6$，且每个周期前$5$项固定为$1、1、2、1、1$。
而第$6$项也是有规律的，$8$出现的周期为$2$，$16$出现的周期为$4$，$32$出现的周期为$8$……
即$4?2^i$出现的周期为$2^i$，$i=1,2,3\dots \dots$
这样就可以快速求出$lowbit(Fi{b}_n)$的前$n$项和$ans2$了，最后的答案即$ans1?ans2$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;long long lowbit(long long x){
    return x&(-x);}
const long long MOD=998244353;
long long n;
long long b[100];
struct node
{
    long long g[5][5];
}f,res;
void init(node &x)//构造单位矩阵
{
    for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(i==j)x.g[i][j]=1;else x.g[i][j]=0;
}
void multiple(node &x,node &y,node &z)//矩阵乘法运算
{
    memset(z.g,0,sizeof(z.g));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(x.g[i][j]){
    for(int k=1;k<=3;k++){
    z.g[i][k]+=x.g[i][j]*y.g[j][k];z.g[i][k]%=MOD;}}
}
void quickpow(long long k)//快速幂
{
    init(res);node temp=f,t;while(k){
    if(k&1){
    multiple(res,temp,t);res=t;}multiple(temp,temp,t);temp=t;k>>=1;}
}
long long solve()
{
    if(n<=1)return 1;quickpow(n-1);long long ret=res.g[1][1]*1+res.g[1][2]*1;ret%=MOD;ret+=res.g[1][3]*1;ret%=MOD;return ret;
}
int T;
int main()
{
    scanf("%d",&T);while(T--){
    scanf("%lld",&n);f.g[1][1]=1;f.g[1][2]=1;f.g[1][3]=0;f.g[2][1]=0;f.g[2][2]=1;f.g[2][3]=1;f.g[3][1]=0;f.g[3][2]=1;f.g[3][3]=0;long long ans1=solve();//printf("%lld\n",ans1);long long p=n/6;long long ans2=p*6%MOD;switch(n%6){
    case 1:ans2+=1;break;case 2:ans2+=2;break;case 3:ans2+=4;break;case 4:ans2+=5;break;case 5:ans2+=6;break;}b[0]=1;for(int i=1;i<=62;i++)b[i]=b[i-1]*2;for(int i=0;i<=62;i++){
    long long q=p-b[i];if(q<0) break;ans2+=(q/b[i+1]+1)*b[i]*8;ans2%=MOD;}//printf("%lld\n",ans2);printf("%lld\n",(ans1-ans2+MOD)%MOD);}return 0;
}