解决思路

问题分析：
题目要求将正整数分解为2的幂次方的和，并按照特定格式输出。例如，137分解为2^7+2^3+2^0，需要递归展开每个指数，最终表示为2(2(2)+2+2(0))+2(2+2(0))+2(0)。

关键思路：

1. ​二进制分解：将数字分解为2的幂次方的和，通过位运算提取各个指数。
2. ​递归处理：对每个指数递归分解，直到指数为0或1。
3. ​字符串拼接：将分解后的结果按格式拼接，用+连接各幂次项。

---

解决步骤

1. ​分解输入数：将输入数按二进制分解为2的幂次方的指数。
2. ​递归处理指数：对每个指数递归生成其字符串表示：
   • 若指数为0，返回2(0)。
   • 若指数为1，返回2。
   • 若指数≥2，递归分解后包裹为2(...)。
3. ​拼接结果：将所有项的字符串按+连接，形成最终表达式。

---

图示步骤

以输入n=137为例：

1. ​分解为2的幂次方：137 = 128 + 8 + 1 → 对应指数7, 3, 0。
2. ​递归处理指数7：
   • 7 = 4 + 2 + 1 → 指数2, 1, 0。
   • 递归处理2 → 2(2)，1 → 2，0 → 2(0)。
   • 拼接为2(2(2)+2+2(0))。
3. ​最终结果：所有项拼接为2(2(2)+2+2(0))+2(2+2(0))+2(0)。

---

完整代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 递归生成幂次方表达式字符串
string dfs(int k) {
    if (k == 0) return "0";
    if (k == 1) return ""; // 指数为1时直接返回空字符串，外层拼接为"2"
    
    vector<int> exponents; // 存储当前数的二进制分解指数
    int highest = 0;
    while ((1 << (highest + 1)) <= k) { // 找到最大的指数
        highest++;
    }
    
    // 从最高位到最低位检查每一位是否为1
    for (int i = highest; i >= 0; --i) {
        if (k & (1 << i)) {
            exponents.push_back(i);
        }
    }
    
    string res;
    for (int i = 0; i < exponents.size(); ++i) {
        int m = exponents[i];
        string term;
        if (m == 0) { // 指数为0，直接拼接"2(0)"
            term = "2(0)";
        } else if (m == 1) { // 指数为1，直接拼接"2"
            term = "2";
        } else { // 指数≥2，递归处理并包裹为2(...)
            term = "2(" + dfs(m) + ")";
        }
        
        if (i != 0) { // 非第一项前添加"+"
            res += "+";
        }
        res += term;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> exponents; // 存储输入数的二进制分解指数
    int temp = n;
    int highest = 0;
    while ((1 << (highest + 1)) <= temp) { // 找到最大的指数
        highest++;
    }
    
    // 从最高位到最低位检查每一位是否为1
    for (int i = highest; i >= 0; --i) {
        if (temp & (1 << i)) {
            exponents.push_back(i);
        }
    }
    
    string result;
    for (int i = 0; i < exponents.size(); ++i) {
        int m = exponents[i];
        string term;
        if (m == 0) { // 指数为0，直接拼接"2(0)"
            term = "2(0)";
        } else if (m == 1) { // 指数为1，直接拼接"2"
            term = "2";
        } else { // 指数≥2，递归处理并包裹为2(...)
            term = "2(" + dfs(m) + ")";
        }
        
        if (i != 0) { // 非第一项前添加"+"
            result += "+";
        }
        result += term;
    }
    
    cout << result << endl;
    return 0;
}

---

关键代码注释

1. ​二进制分解：

   while ((1 << (highest + 1)) <= k) { ... } // 找到最大的指数

   通过位运算确定当前数的二进制最高位。

2. ​递归终止条件：

   if (k == 0) return "0";
   if (k == 1) return ""; // 外层拼接为"2"

   指数为0或1时直接返回对应字符串，结束递归。

3. ​字符串拼接：

   term = "2(" + dfs(m) + ")"; // 递归处理指数并包裹为2(...)

   递归调用生成子表达式，并按格式拼接。

---

时间复杂度

• ​时间复杂度：O(log n * log m)，其中m为递归过程中分解的指数。
  每个数的二进制位数为O(log n)，递归深度为O(log m)，总复杂度为多项式级，可高效处理大数。

---

总结

该问题通过递归分解二进制表示的指数，将其转换为特定格式的字符串。代码利用位运算快速分解数字，并通过递归处理嵌套格式，确保输出的严格匹配。核心在于正确处理递归终止条件和字符串拼接逻辑，保证结果的正确性和格式的规范性。