题目大意
给出一个公式，f(1)=1，对任意正整数n有3×f(n)×f(2n+1)=f(2n)×(1+3f(n)),f(2n)<6×f(n)。
给一个n和k，设g( i )=∑(f( j ) mod k=i)( 0<=i<k, 1<=j<=n ) , 求g(0)g(1)...^g(k-1)的值。
n<=10^18, k是3,5,17,257,65537中的一个。
解答
题目的公式写的有点吓人，其实仔细观看或推导前几项就会发现f[2n]=3f[n]和f[2n+1]=3f[n]+1的递推公式。我先是想打表找规律，发现mod 3很快就找到了，但是mod 5找不到，更何况还有mod更大的。
换个思路就会发现，f(n)的递推可以分段，分成[1,1]，[2,3]，[4,7]，...，[2k,2(k+1)-1]。最多只有logn个区间，对每个区间存mod的余数的状态，就可以转移。把[1,n]的区间分成[1,2k-1]和[2k,n] ( 2^k恰好小于等于n )，做两次分段dp就可以了( 第二次要注意区间上界，记录区间最后一个f(n)取mod的值 )。
网上题解有种神奇的做法，推出递推公式后，f(n)其实是把n转化成二进制后，1的权重按三进制来算。比如f(5)=10，5的二进制是101，30+32=10。然后直接数位dp做。
参考blog1
参考blog2
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define bll long long
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
const int maxL=65537+10;
long long N;
int modd;
long long dp[65][maxL];
long long G[maxL];
void baoli()
{
static int f[maxL];
static int gg[maxL];
Mem(gg,0);
f[1]=1;
gg[1]=1;
for (int i=2; i<=N; i++)
{
if (i&1) f[i]=(f[i>>1]*3+1) %modd;
else f[i]=(f[i>>1]*3) %modd;
gg[f[i]]++;
}
int ans=0;
For(i,0,modd-1)
ans^=gg[i];
printf("%d\n",ans);
}
void Done1(long long *G,long long tt)
{
Mem(dp,0);
dp[0][1]=1;
G[1]++;
for (int k=1; (1LL<<k)<=tt; k++)
{
For(j,0,modd-1)
if (dp[k-1][j])
{
int ss=3*j %modd;
dp[k][ss]+=dp[k-1][j];
dp[k][(ss+1)%modd]+=dp[k-1][j];
}
For(j,0,modd-1)
G[j]+=dp[k][j];
}
}
void Done2(long long *G,long long x,long long y)
{
static long long low[65],high[65]; // 存每个区间的上下界
static int last_mod[65]; // 记录区间最后一个数的取mod值
int k=0;
low[k]=x,high[k]=y;
for (long long tt=x>>1; tt; tt>>=1)
{
k++;
low[k]=low[k-1]>>1;
high[k]=high[k-1]>>1;
}
Mem(dp,0);
last_mod[k]=1;
dp[k][1]=1;
for (k--; k>=0; k--)
{
For(j,0,modd-1)
if (dp[k+1][j])
{
int ss=3*j %modd;
dp[k][ss]+=dp[k+1][j];
dp[k][(ss+1)%modd]+=dp[k+1][j];
}
if (!(high[k]&1))
{
int ss=(last_mod[k+1]*3+1) %modd;
dp[k][ss]--;
}
last_mod[k]=(last_mod[k+1]*3+(high[k]&1)) %modd;
}
For(j,0,modd-1)
G[j]+=dp[0][j];
}
long long Done()
{
if (N==1) return 1;
long long r=1;
while((r<<1)<=N) r<<=1;
memset(G,0,sizeof(long long)*(modd+2)); // G[]存余数的个数
Done1(G,r>>1); // 计算从区间[1,1]到[r/2,r-1]的和
Done2(G,r,N); // 计算[r,N]的和
long long ans=0;
For(j,0,modd-1)
ans^=G[j];
return ans;
}
int main(int argc, char* argv[])
{
int zz=0; scanf("%d",&zz);
For(test,1,zz)
{
scanf("%lld%d",&N,&modd);
bll ans=Done();
printf("%lld\n",ans);
//baoli(); // 暴力 验算
}
return 0;
}
