[NOIP 1998 普及组] 幂次方

知识点

递归、二进制表示

解题思路

把n的二进制为1的各位从高到低输出。第k位对应2的k次幂：k=0输出2(0)，k=1输出2，其余输出2(递归表示k)，不同项用加号连接。递归参数为0时返回字符串0。

正确性说明

二进制展开把正整数唯一分解为不同二次幂之和。算法按规定输出每项，指数递归使用同样的唯一展开；指数严格小于原参数，递归终止，归纳可得整个表示满足约定。

易错点

不能输出2(1)；最高位到最低位；加号只能出现在两项之间；输出不得夹空格。

复杂度

递归参数最多约log n层内快速缩小，耗时随输出长度加各次位扫描增长；n≤20000，额外空间为递归和输出。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
string f(int n){if(!n)return "0";string s;for(int k=14;k>=0;k--)if(n>>k&1){if(!s.empty())s+='+';if(k==1)s+="2";else s+="2("+f(k)+")";}return s;}int main(){int n;cin>>n;cout<<f(n)<<'\n';}