自动搬运

查看原文

来自洛谷，原作者为

	过氧化氢_syq0057 七色评测结果 https://www.luogu.com.cn/problem/U170829

搬运于2025-08-24 22:37:52，当前版本为作者最后更新于2023-11-08 20:01:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题外话

很好的题，只不过是冲着分块标签来的发现不是分块 /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;
}