[HihoCoder1259]A Math Problem

题目大意：
　　有一个函数f(n)，满足3f(n)*f(2n+1)=f(2n)*(1+3f(n)),f(2n)<6f(n)。
　　我们用g(t)表示f(i)%k=t的i的个数，其中1<=i<=n。
　　问对于0<=x<k，所有的g(x)的异或和。

思路：
　　将函数用递推式表示为：
　　f(2n)=3f(n)
　　f(2n+1)=f(2n)+1
　　也就是说f(n)就是将n的二进制数串当作一个三进制数来算的值。
　　接下来就是一个简单的数位DP。
　　f[i][j]表示DP到第i位，前面那么多数所构成的三进制的值在模k意义下的值。

#include<cstdio>
#include<cctype>
#include<cstring>
typedef long long int64;
inline int64 getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int64 x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int K=65537;
inline int log2(const float &x) {
    return ((unsigned&)x>>23&255)-127;
}
int64 f[2][K];
inline int64 calc(const int64 &n,const int &k) {
    int sum=0;
    const int len=log2(n);
    memset(f[len&1],0,sizeof *f);
    for(register int i=len;i>=0;i--) {
        memset(f[!(i&1)],0,sizeof *f);
        const int cur=n>>i&1;
        sum=(sum*3)%k;
        for(register int j=0;j<cur;j++) {
            f[i&1][(sum+j)%k]++;
        }
        sum=(sum+cur)%k;
        for(register int j=0;j<k;j++) {
            f[!(i&1)][j*3%k]+=f[i&1][j];
            f[!(i&1)][(j*3+1)%k]+=f[i&1][j];
        }
    }
    f[0][0]--;
    f[0][sum]++;
    int64 ans=0;
    for(register int i=0;i<k;i++) {
        ans^=f[0][i];
    }
    return ans;
}
int main() {
    for(register int T=getint();T;T--) {
        int64 n=getint();
        int k=getint();
        printf("%lld
",calc(n,k));
    }
    return 0;
}