題目大意
給出一個(gè)公式，f(1)=1浓若，對(duì)任意正整數(shù)n有3×f(n)×f(2n+1)=f(2n)×(1+3f(n)),f(2n)<6×f(n)渺杉。
給一個(gè)n和k，設(shè)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中的一個(gè)是越。
解答
題目的公式寫的有點(diǎn)嚇人，其實(shí)仔細(xì)觀看或推導(dǎo)前幾項(xiàng)就會(huì)發(fā)現(xiàn)f[2n]=3f[n]和f[2n+1]=3f[n]+1的遞推公式碌上。我先是想打表找規(guī)律倚评，發(fā)現(xiàn)mod 3很快就找到了浦徊，但是mod 5找不到，更何況還有mod更大的天梧。
換個(gè)思路就會(huì)發(fā)現(xiàn)盔性，f(n)的遞推可以分段，分成[1,1]腿倚，[2,3]纯出，[4,7]，...敷燎，[2k,2(k+1)-1]暂筝。最多只有l(wèi)ogn個(gè)區(qū)間，對(duì)每個(gè)區(qū)間存mod的余數(shù)的狀態(tài)硬贯，就可以轉(zhuǎn)移焕襟。把[1,n]的區(qū)間分成[1,2k-1]和[2k,n] ( 2^k恰好小于等于n )，做兩次分段dp就可以了( 第二次要注意區(qū)間上界饭豹，記錄區(qū)間最后一個(gè)f(n)取mod的值 )鸵赖。
網(wǎng)上題解有種神奇的做法，推出遞推公式后拄衰，f(n)其實(shí)是把n轉(zhuǎn)化成二進(jìn)制后它褪，1的權(quán)重按三進(jìn)制來算。比如f(5)=10翘悉，5的二進(jìn)制是101茫打，30+32=10。然后直接數(shù)位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]; // 存每個(gè)區(qū)間的上下界
static int last_mod[65]; // 記錄區(qū)間最后一個(gè)數(shù)的取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[]存余數(shù)的個(gè)數(shù)
Done1(G,r>>1); // 計(jì)算從區(qū)間[1,1]到[r/2,r-1]的和
Done2(G,r,N); // 計(jì)算[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(); // 暴力 驗(yàn)算
}
return 0;
}
