题意：定义一个 \(\mathbb{N}\to\mathbb{N}\) 的函数 \(f(x)=\begin{cases}1&x=0\\f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{3}\rfloor)&\text{otherwise}\end{cases}\)，求 \(f(n)\)。\(n\le 10^{18}\)。
很容易想到暴力求解，形成 \(\log(n)\) 层的二叉树，复杂度为 \(O(n)\)，无法通过。
做法 1
注意到，有 \(\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{3}\rfloor=\lfloor\frac{\lfloor\frac{n}{3}\rfloor}{2}\rfloor\)，所以实际有用的状态数只有 \(\log^2 n\) 个（每层比上一层增加一个状态）。于是可以记忆化搜索，用 map 当 DP 数组即可。
By cxm1024
#include<bits/stdc++.h>
using namespace std;
map<long long,long long> m;
long long solve(long long x) {
if(m[x]) return m[x];
return m[x]=solve(x/2)+solve(x/3);
}
signed main() {
long long n;
scanf("%lld",&n);
m[0]=1;
printf("%lld\n",solve(n));
return 0;
}
做法 2
可以考虑问题转化为：\(n\) 每次除以二或除以三，问有多少种操作序列能到 \(0\)，然后用组合数求解即可。我们枚举用了 \(i\) 次除以二，再算出此时还需要的除以三的次数 \(j\)，计算 \(\binom{i+j}{i}\) 即可。
By ygussany
#include <stdio.h>
typedef struct List {
struct List *next;
long long v, ans;
} list;
#define HASH 1000003
const int H_Mod = HASH;
int hn = 0;
list *hash[HASH] = {}, hd[1000000];
long long recursion(long long N)
{
if (N == 0) return 1;
int h = N % H_Mod;
list *hp;
for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == N) return hp->ans;
hp = &(hd[hn++]);
hp->v = N;
hp->ans = recursion(N / 2) + recursion(N / 3);
return hp->ans;
}
long long comb[61][61];
long long solve(long long N)
{
int k, l;
long long X, ans = 2;
for (k = 1, X = 2; X * 2 <= N; k++, X <<= 1);
for (l = 0; k > 0; ) {
k--;
X >>= 1;
while (X * 3 <= N) {
l++;
X *= 3;
}
ans += comb[k+l][k] + ((X * 2 > N)? comb[k+l][k]: 0);
}
return ans;
}
int main()
{
long long N;
scanf("%lld\n", &N);
if (N == 0) {
printf("1\n");
return 0;
} else if (N == 1) {
printf("2\n");
return 0;
}
int i, j;
for (i = 1, comb[0][0] = 1; i <= 60; i++) for (j = 1, comb[i][0] = 1, comb[i][i] = 1; j < i; j++) comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
printf("%lld\n", solve(N));
fflush(stdout);
return 0;
}
做法 3
与做法 1 类似，不使用记忆化搜索，改为预处理出所有状态（离散化），然后直接 DP。
#include<stdio.h>
long long int h[1000006], l;
int comp_h(long long int a, long long int b)
{
if (h[a] < h[b])
return 1;
else
return -1;
}
void swap_h(long long int a, long long int b)
{
long long int f = h[a];
h[a] = h[b];
h[b] = f;
return;
}
void push(long long int ne)
{
h[l] = ne;
long long int p = l;
l++;
for (; p > 0; p = (p - 1) / 2)
if (comp_h((p - 1) / 2, p) > 0)
swap_h((p - 1) / 2, p);
return;
}
long long int pop()
{
l--;
swap_h(0, l);
long long int p = 0;
for (;;)
{
if (2 * p + 2 < l)
{
if (comp_h(2 * p + 1, 2 * p + 2) > 0)
{
if (comp_h(p, 2 * p + 2) > 0)
swap_h(p, 2 * p + 2);
p = 2 * p + 2;
}
else
{
if (comp_h(p, 2 * p + 1) > 0)
swap_h(p, 2 * p + 1);
p = 2 * p + 1;
}
}
else if (2 * p + 1 < l)
{
if (comp_h(p, 2 * p + 1) > 0)
swap_h(p, 2 * p + 1);
p = 2 * p + 1;
}
else
break;
}
return h[l];
}
long long int s[1000006], v[1000006], ss;
long long int fined(long long int x)
{
long long int min, mid, max;
min = -1;
max = ss;
while (max - min > 1)
{
mid = (max + min) / 2;
if (s[mid] < x)
max = mid;
else
min = mid;
}
return v[min];
}
int main()
{
long long int n;
scanf("%lld", &n);
long long int i;
s[0] = n;
ss = 1;
l = 0;
push(n / 2);
push(n / 3);
while (l > 0)
{
i = pop();
if (s[ss - 1] == i)
continue;
s[ss] = i;
ss++;
push(i / 2);
push(i / 3);
}
v[ss - 1] = 1;
for (i = ss - 2; i >= 0; i--)
v[i] = fined(s[i] / 2) + fined(s[i] / 3);
printf("%lld\n", v[0]);
return 0;
}