题解 P8308 〈 TREEのOI 2022 Spring 〉Counting By Ternary

· · 题解

题外话

很好的题，只不过是冲着分块标签来的发现不是分块 /ll。

Solution

手动画几个图可以发现，一个节点 i 好像只连向 \lfloor \log_3{i} \rfloor+1 的节点，所以我们可以很快推出递推式：

f_i= \sum_{j=1}^{\lfloor \log_3i \rfloor +1} f_j

以下是核心代码

int main() {
    scanf("%lld%lld", &p, &q);
    ll x = q * Log3(p) + 1;//这里手写log3
    f[1] = 1, f[2] = 1;
    for (ll i=3; i<=x; i++)
        for (ll j=1; j<=Log3(i)+1; j++)
            f[i] += f[j];
    for (ll i=1; i<=x; i++)
        ans += f[i];
    printf("%lld\n", ans);
}

这样就能得到 20pts 了。

这种算法我们时间复杂度是 O(\log_3{p^q}) 即为 O(3^{35}) 的，考虑优化。

观察到 f_i 有很长一段相同的取值（因为 \lfloor \log_3i \rfloor +1 限制了它的发挥）。

f_1=f_2=1 f_3=f_4=...=f_8=2 f_9=f_{10}=...=f_{26}=4 f_{27}=f_{28}=...=f_{80}=6

于是我们设 g_i 代表 f_{3^{i-1}} 到 f_{3^i-1} 的值。

g_1=f_1=f_2=1 g_2=f_3=f_4=...=f_8=2 g_i=f_{3^{i-1}}=...=f_{3^{i}-1}

根据一开始的公式，显然（把 f_i 推到 g_i 上）

g_i= \sum_{j=1}^i f_i

令 x=\log_3p^q，所以

ans= \sum_{i=1}^x f_i= \sum_{j=1}^{\lfloor \log_3i \rfloor +1} g_j \times (3^j-3^{j-1})

注意对 g_n 特殊处理（最后一项只能到 q \times \lfloor \log_3p \rfloor + 1）

这样，我们就在 O(\log_3 \log_3p^q) 内即 O(35) 内处理，就可过了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
const int N = 2000005;
const int M = 200005;
#define ll long long
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
inline int read() {
    int x = 0, f = 1; char ch;
    ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * f;
}
ll p, q;
ll f[N], g[N];
ll ans;
ll Log3(ll s) {//下取整 
    ll res = 0;
    while (s) {
        s /= 3;
        res++;
    }
    return res - 1;
}
ll ksm(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}
int main() {
    scanf("%lld%lld", &p, &q);
    ll x = q * Log3(p) + 1;
    ll log3x = Log3(q * Log3(p)) + 1;
    f[1] = 1, f[2] = 1;
    for (int i=3; i<=100; i++)
        for (int j=1; j<=Log3(i)+1; j++)
            f[i] += f[j];
    g[1] = 1, g[2] = 2;
    for (ll i=3; i<=log3x; i++)
        for (int j=1; j<=i; j++)
            g[i] += f[j];
    for (int i=1; i<=log3x; i++) {
        if (i == log3x) ans += (x - ksm(3, i - 1) + 1) * g[i];//注意特殊处理
        else ans += (ksm(3, i) - ksm(3, i - 1)) * g[i];
    }
    printf("%lld\n", ans);
    return 0;
}