在实在写不出来后，窝不要脸的点开了OEIS，得到了“a(n)=if(n<2, 0, if(n%2==0, 3*a(n/2)+n/4*(n/2-1), 2*a((n-1)/2)+a((n+1)/2)+((n-1)/4)*((n+1)/2)))”打出来代码就很简洁了。

int n=read(),mod=1e6+3;
unordered_map<int,int>mp;

int js(int a){
    if(mp.count(a))return mp[a];
    if(a&1)return mp[a]=(js(a>>1)<<1)+js(a+1>>1)+((a>>1)*(a+1>>1)>>1)%mod;
    else return mp[a]=(js(a>>1)*3+((a>>1)*((a>>1)-1)>>1))%mod;
}

signed main(){
    mp[0]=mp[1]=mp[2]=0;
    print(js(n)),puts("");
    return ~EOF;
}

但是WA掉了三个点，突然想到longlong会乘爆，于是又不要脸的开了int128，但还是WA掉了#1

求助QWQ

int n=read(),mod=1e6+3;
unordered_map<int,int>mp;

int js(int a){
    if(mp.count(a))return mp[a];
    if(a&1)return mp[a]=(js(a>>1)<<1)+js(a+1>>1)+((__int128)(a>>1)*(a+1>>1)>>1)%mod;
    else return mp[a]=(js(a>>1)*3+((__int128)(a>>1)*((a>>1)-1)>>1))%mod;
}

signed main(){
    mp[0]=mp[1]=mp[2]=0;
    print(js(n)),puts("");
    return ~EOF;
}

放心我有define int longlong