[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^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int K=;

 inline int log2(const float &x) {

     return ((unsigned&)x>>&)-;

 }

 int64 f[][K];

 inline int64 calc(const int64 &n,const int &k) {

     int sum=;

     const int len=log2(n);

     memset(f[len&],,sizeof *f);

     for(register int i=len;i>=;i--) {

         memset(f[!(i&)],,sizeof *f);

         const int cur=n>>i&;

         sum=(sum*)%k;

         for(register int j=;j<cur;j++) {

             f[i&][(sum+j)%k]++;

         }

         sum=(sum+cur)%k;

         for(register int j=;j<k;j++) {

             f[!(i&)][j*%k]+=f[i&][j];

             f[!(i&)][(j*+)%k]+=f[i&][j];

         }

     }

     f[][]--;

     f[][sum]++;

     int64 ans=;

     for(register int i=;i<k;i++) {

         ans^=f[][i];

     }

     return ans;

 }

 int main() {

     for(register int T=getint();T;T--) {

         int64 n=getint();

         int k=getint();

         printf("%lld\n",calc(n,k));

     }

     return ;

 }

巴特西

[HihoCoder1259]A Math Problem

最新文章

热门文章