ZYF052 砍竹子
大约 3 分钟数学
ZYF052 砍竹子
【算法标签】 数学推导/贪心
【语法标签】 :快速幂、位运算
有一根长度为 (正整数)的竹子,需要将其砍成若干段,每段长度均为正整数。求所有段长度乘积的最大值,答案需要对 取模。
数据范围:。
二、解题思路
数据规模分析
最大可达 ,意味着不能使用 的枚举或 DP 做法,需要 的数学解法。
贪心策略推导
这是一个经典的整数拆分问题:将一个正整数拆分为若干正整数之和,使乘积最大。
先从小的 开始找规律:
| 拆分方案 | 乘积 | |
|---|---|---|
| 1 | 1(不拆) | 1 |
| 2 | 2(不拆) | 2 |
| 3 | 3(不拆) | 3 |
| 4 | 2+2 | 4 |
| 5 | 2+3 | 6 |
| 6 | 3+3 | 9 |
| 7 | 3+2+2 | 12 |
| 8 | 3+3+2 | 18 |
| 9 | 3+3+3 | 27 |
| 10 | 3+3+2+2 | 36 |
| 11 | 3+3+3+2 | 54 |
| 12 | 3+3+3+3 | 81 |
观察规律:
- 不要拆出 1:拆出 1 对乘积没有贡献(),白白浪费长度。
- 尽量多拆 3:比较 2 和 3 的"性价比"——同样长度下,3 的乘积更大。例如长度 6:拆成 得 ,拆成 得 ,。
- 遇到余 1 时借位:如果 ,比如 ,按"全拆 3"会拆成 ,乘积只有 。但 乘积为 ,更大。所以当余 1 时,少拆一个 3,剩下的 4 拆成 。
为什么不能拆出大于 3 的数?
假设拆出 4,(不劣于 4), 但 1 不好。实际上 乘积一样是 4,但统一用"全拆 3"的公式更方便处理。
假设拆出 5,,所以 5 拆成 2+3 更优。
更大的数同理,都可以进一步拆分成 2 和 3 的组合使乘积更大。所以最优拆分中只会出现 2 和 3。
算法流程
直接根据 的三种情况处理:
设 cnt = n / 3, rem = n % 3
情况1: rem == 0 → 全拆3,乘积 = 3^cnt
情况2: rem == 1 → 少拆一个3,剩下的4拆成2+2,乘积 = 3^(cnt-1) * 4
情况3: rem == 2 → 乘积 = 3^cnt * 2特殊情况: 时(不拆或仅一段),乘积就是 本身(不用取模前):
- :答案为
- :答案为
- :答案为
快速幂取模
可达 , 的幂次高达 ,必须用快速幂(二分幂)在 时间内计算 。
快速幂原理:( 为偶数),( 为奇数)。
手动模拟样例
:
- ,
- 乘积 =
- 对 取模, 不变
- 输出 ,与样例一致
:
- ,
- 乘积 =
- 验证:,乘积 ,正确
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
// 快速幂:计算 a^b % MOD
long long qpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) { // b 是奇数,多乘一个 a
res = res * a % MOD;
}
a = a * a % MOD; // a 平方
b >>= 1; // b 右移一位,相当于 b /= 2
}
return res;
}
int main() {
long long n;
cin >> n;
// 特殊情况:n <= 3 时直接返回 n
if (n <= 3) {
cout << n % MOD << endl;
return 0;
}
long long cnt = n / 3; // 能拆出多少个 3
long long rem = n % 3; // 余数
long long ans;
if (rem == 0) {
// 全拆 3:3^cnt
ans = qpow(3, cnt);
} else if (rem == 1) {
// 余 1:少一个 3,剩下 4 拆成 2+2
// 3^(cnt-1) * 4
ans = qpow(3, cnt - 1) * 4 % MOD;
} else {
// 余 2:3^cnt * 2
ans = qpow(3, cnt) * 2 % MOD;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:快速幂每次将指数折半,共 次循环,非常高效, 也只需约 30 次运算。
- 空间复杂度:仅使用几个变量,。
