ABC275D. Yet Another Recursive Function题解

发表于 分类于

题目传送门

题意：定义一个 N→N\mathbb{N}\to\mathbb{N} 的函数 f(x)={1x=0f(⌊x2⌋)+f(⌊x3⌋)otherwisef(x)=\begin{cases}1&x=0\\f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{3}\rfloor)&\text{otherwise}\end{cases}，求 f(n)f(n)。n≤1018n\le 10^{18}。

很容易想到暴力求解，形成 log⁡(n)\log(n) 层的二叉树，复杂度为 O(n)O(n)，无法通过。

做法 1

注意到，有 ⌊⌊n2⌋3⌋=⌊⌊n3⌋2⌋\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{3}\rfloor=\lfloor\frac{\lfloor\frac{n}{3}\rfloor}{2}\rfloor，所以实际有用的状态数只有 log⁡2n\log^2 n 个（每层比上一层增加一个状态）。于是可以记忆化搜索，用 map 当 DP 数组即可。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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

可以考虑问题转化为：nn 每次除以二或除以三，问有多少种操作序列能到 00，然后用组合数求解即可。我们枚举用了 ii 次除以二，再算出此时还需要的除以三的次数 jj，计算 (i+ji)\binom{i+j}{i} 即可。

By ygussany

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
57
58
59
60
61
62
63
#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。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#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;
}