//硬币问题 转化为二进制 //对于（7）111这类只有一种解法 //对于111.1000.0连续n个1,m个0的共有n * m +1种解法 //然后把二进制串分为x个连续的（11.100.0） //最左的一个(11.100.0) ans[0] = n0 * m0 +1; //先计算最右边两个 (11.100.0)(11.100.0),设有n1个1，m1个0；n0个1，m0个0，那么有 // ans[1] = (n1*m1+1)* (n0*m0+1) + m0中解法； //然后再和左边一个10串计算ans[2] = (n2*m2+1)* ans[1] + m1*ans[0]+ m0; //从优向左依次计算 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { unsigned long long n; while(cin >> n) { vector<int> num; long long onezero[30][2]; long long ans[30]; while(n) { num.push_back( n & 1); n = n >> 1; } // for(int i = num.size()-1; i >=0; --i) // { // cout <<num[i]; // } // cout <<endl; int pair01 = 0; int cnt0 = 0; int cnt1 = 0; bool flag; while((flag = num.front())&& !num.empty()) { num.erase(num.begin()); } if(num.empty()) { cout << 1 <<endl; } else { for(int i = 0; i < num.size(); ++i) { if(num[i] == 1) { if(!flag) { onezero[pair01][0] = cnt0; cnt0 = 0; flag = true; } ++cnt1; if( i == num.size()-1) { onezero[pair01][1] = cnt1; } } else { if(flag) { onezero[pair01++][1] = cnt1; cnt1 = 0; flag = false; } ++cnt0; } } ans[0] = onezero[0][1] * onezero[0][0] +1; for(int k = 1; k <= pair01; ++k) { int join = onezero[0][0]; for(int j = 1; j < k; ++j) { join += onezero[j][0] * ans[j-1]; } ans[k] = (onezero[k][1] * onezero[k][0] +1) * ans[k-1] + join; } cout << ans[pair01]<<endl; } } return 0; }