明天就要去实验室干活了。。。。下次再打题不知是何时。。。。
题目链接：
http://hihocoder.com/contest/hihointerview11/problem/2
这题不难，一开始想错了。。。。其实并不复杂，从低位到高位，逐个1处理。
我用了个简单dp。
先将n转化成二进制。
我们划分出每个1+x个0的情况（x可为0）。
对于单个模块假设有s0[i+1]种情况，在前一个模块退一个1的情况下有s1[i+1]中情况。（这是有规律的）
假设不进位的情况下情况数：dp[0][i]
进位的情况下情况数：dp[1][i]
这样得到转移方程：dp[0][i+1] = s0[i+1]*dp[0][i] + dp[1][i]
dp[1][i+1] = s1[i+1]*dp[0][i] + dp[1][i]
AC代码：
#include <bits/stdc++.h> using namespace std;
const int maxn = ; int p[maxn];
typedef long long int64; int64 dp[][maxn]; int main(void){
int n;
scanf("%d", &n); if(n == ){
printf("1\n");
}else{
int cnt = ;
while(n){
p[cnt++] = n%;
n >>= ;
} vector<int> v;
int t = ;
for(int i = ; i < cnt; ++i){
if(p[i] == ){
t++;
}else{
v.push_back(t);
t = ;
}
}
//cout << "haha" << endl; int sz = v.size();
int64 ans;
dp[][] = v[], dp[][] = v[]-;
for(int i = ; i < sz; ++i){
dp[][i] = v[i]*dp[][i-] + dp[][i-];
dp[][i] = (v[i]-)*dp[][i-] + dp[][i-];
}
/*for(int i = 0; i < sz; ++i)
cout << dp[0][i] << " " << dp[1][i] << endl;*/
ans = dp[][sz-]; printf("%lld\n", ans);
} return ;
}