[UVALive7271]A Math Problem

又见数位dp。

题目链接及题目大意:定义一个函数$f(x)$, $f(1)=1$,对于任意的正整数$n$,有:
$3*f(n)*f(2n+1)=f(2n)*(1+3f(n)),f(2n)<6f(n)$。
同时定义一个函数$g(t)$,$g(t)=\sum f(i) \space mod \space k=t$。
问$g(0)\bigoplus g(1)\bigoplus … \bigoplus g(k-1)$的值。

首先需要推出$f(x)$的原式:
$$
3*f(n)*f(2n+1)=f(2n)*(1+3f(n)) \\
3*f(n)*f(2n+1)=f(2n)+3*f(2n)*f(n) \\
f(2n+1)=\frac{f(2n)}{3*f(n)}+f(2n) \\
$$
由题意得,$f(x)$为整数函数,且$f(2n)<6f(n)$,因此可以推出:
$$
\begin{cases}
f(1)=1 \\
f(i)=3f(\frac{i}{2}) \space \space\space\space\space\space \space\space\space\space\space \space\space\space\space i为偶数 \\
f(i)=f(i-1)+1 \space\space\space\space\space i为奇数
\end{cases}
$$
首先我们看$i$为偶数的情况,发现当$i$扩大两倍时,$f(i)$扩大三倍,如果将$x,f(x)$,分别看作二进制形式和三进制形式,则扩大倍数的情况可以修改为:当$i$左移一位时,$f(i)$也左移一位,当$i+1$时,$f(i)$也加一。看$f(x)$的前几项能够发现:
$$
f(1)=1 -> f((1)_2)=(1)_3 \\
f(2)=3 -> f((10)_2)=(10)_3 \\
f(3)=4 -> f((11)_2)=(11)_3\\
f(4)=9 -> f((100)_2)=(100)_3 \\
f(5)=10 -> f((101)_2)=(101)_3 \\
f(6)=12 -> f((110)_2)=(110)_3 \\
f(7)=13 -> f((111)_2)=(111)_3 \\
f(8)=27 -> f((1000)_2)=(1000)_3 \\
f(9)=28 -> f((1001)_2)=(1001)_3 \\

$$
发现规律之后,就可以用数位dp的做法来求解$g(t)$的值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#pragma comment(linker, "/STACK:10240000,10240000")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=70000+10;
const int INF=0x3f3f3f3f;
int t,k,cur;
ll n;
int bits[65];
int fac[65];
ll dp[5][65][maxn];//第k个模数,第i位余数为j的方案数
map<int,int>mp;
void init(){
mp[3]=0;
mp[5]=1;
mp[17]=2;
mp[257]=3;
mp[65537]=4;
memset(dp,-1,sizeof(dp));
fac[0]=1;
}
ll dfs(int pos,int last,bool limit){//last为满足条件的当前余数
if(pos==0) return last==0;
if(!limit && dp[cur][pos][last]!=-1) return dp[cur][pos][last];

int maxx=limit?bits[pos]:1;
ll sum=0;
for(int i=0;i<=maxx;i++){
sum+=dfs(pos-1,(last-i*fac[pos-1]+k)%k,limit && i==maxx);
}
if(!limit) dp[cur][pos][last]=sum;
return sum;
}
void solve(ll x){
int sum=0;
while(x){
bits[++sum]=x&1;
x>>=1;
}
ll ans=0;
//分步统计每个余数的方案数
for(int i=0;i<k;i++) ans^=dfs(sum,i,1)-(i==0);
printf("%lld\n",ans);
}
int main()
{
init();
scanf("%d",&t);
while(t--){
scanf("%lld %d",&n,&k);
cur=mp[k];
for(int i=1;i<65;i++) fac[i]=fac[i-1]*3%k;//预处理 3^i%k
solve(n);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------