题意：开始序列{1};
一次变换{1，1，2}；
两次变换{1，1，2，1，2，2，3}
。。。
求s[n];
题解：打表 S1，S2，S4，S8，S16，S32。。。。。。
公式 S[n]=S[最近的比其小的2的？次方]+S[n-最近的比其小的2的？次方]+n-n-最近的比其小的2的？次方;
复杂度log（n）；
#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> using namespace std; #define ll __int64 int scan() { int res = 0 , ch ; while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) ) { if( ch == EOF ) return 1 << 30 ; } res = ch - '0' ; while( ( ch = getchar() ) >= '0' && ch <= '9' ) res = res * 10 + ( ch - '0' ) ; return res ; } ll a[80]; ll pow1(ll x, ll y) { ll num=1; for(ll i=0;i<y;i++) { num*=x; } return num; } ll hehe(ll x) { a[0]=1; a[1]=2; ll i,sum=3; for(i=2;i<=x;i++) { a[i]=sum+pow1(2,i)-i; sum+=a[i]; } return a[x]; } ll erfen(ll x) { ll i; if(x==0) return 0; if(x==1) return 1; ll num=1; for(i=1;;i++) { num*=2; if(num>=x) break; } if(num==x) return hehe(i); else return erfen(num/2)+erfen(x-num/2)+x-num/2; } int main() { ll x,y,z,i,t; scanf("%I64d",&x); while(x--) { scanf("%I64d",&y); printf("%I64d ",erfen(y)); } return 0; }