P1010 [NOIP 1998 普及组] 幂次方
记忆化搜索。
#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){int w=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48);ch=getchar();}return w*f;
}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}
const int N=2e4+10;
int n;
string f[N];
string solve(int x){if(!f[x].empty()) return f[x];else if(x==1){return f[x]="2(0)";}else if(x==2){return f[x]="2";}string res="";for(int i=15;i>=0;--i){if((x>>i)&1){string add="2("+solve(i)+")";if(i==0) add="2(0)";else if(i==1) add="2";if(res.empty()) res=add;else res+="+"+add;}}return f[x]=res;
}int main(){#ifndef ONLINE_JUDGE//freopen("in.txt","r",stdin);#endifint n=read();cout<<solve(n)<<endl;#ifndef ONLINE_JUDGEfprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);#endifreturn 0;
}