传送门：http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4976
时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte
描述
我们定义十进制数中有6的为新生数。现在给你一些二进制数，叫你判断是不是新生数。当然这个太简单了，我们换种玩法，给你一个不完全的二进制数，其中有些数字是未知的用x表示，问，这个未知的二进制数最多可以有几种新生数的表示。
输入
输入有多组数据。
每组一行，一个二进制数(长度不超过50，未知的数不超过20)。
输出
每行输出一个数，表示最多可以表示的总数。
样例输入
1xxxxx1111xx0xx
1xx0x1x0x1x0x1x0x1x0x10
样例输出
179
1408
提示
PS：放心没有前导0和x。
思路：
输入字符串，对字符串如果是'x' 则分 x为0或者x为1进行再次深搜。直到整个字符串都是01串（即不包含字符x的时候，return掉就行了）
因为x最多是20，不用担心会爆栈。
然后因为最多是50位，所以数字也不会超过__int64，不用大数
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int su;
bool judge(string s){
for(int i = s.size() - ; i >= ; i--){
if(s[i] == 'x')return false;
}
return true;
}
string s;
bool check(__int64 ans){
while(ans){
int sum = ans % ;
if(sum == ) return true;
ans/=;
}
return false;
}
void dfs(int i,__int64 sum,__int64 w){
if(i == -){
if(check(sum))//check函数判断含不含6
su++;
return;
}
if(s[i] == ''){
dfs(i-,sum,w*);
return;
}//sum 不加当前的数
else if(s[i] == ''){
dfs(i-,sum+w,w*);
return;
}//sum 加当前的数
else{
dfs(i-,sum+w,w*);
dfs(i-,sum,w*);
//分两种情况递归下去
return;
}
}
int main()
{
while(cin>>s){
su = ;
int len = s.size();dfs(len-,,);
printf("%d\n",su);
}
}