本题意思非常明确，就是一道数位dp，纯模板题：没什么好说的，直接上代码：
#include#include #include #include using namespace std;const int maxn = 1<<9;long long A,B;int lvalue;int cnt,limit[10];int binary_index[10];int dp[10][10*maxn];void index_init()///把所有2^n的值保存下来{ binary_index[0]=1; for(int i=1;i<10;i++) { binary_index[i]=2*binary_index[i-1]; } memset(dp,-1,sizeof(dp));///也作为一种标记}void init(){ cnt=0; while(B) { limit[cnt++]=B%10; B/=10; } int cnta=0; lvalue=0; while(A) { lvalue+=(A%10)*binary_index[cnta++]; A/=10; }}int dfs(int bit,int value,bool flag){ int ans=0; if(value<0) return 0; if(bit<0) { if(value>=0) return 1; } if(!flag && dp[bit][value]!=-1)///只有当这位没有范围限制的时候才能够用dp[bit][value] { return dp[bit][value]; } int num = (flag ? limit[bit]:9); for(int i=0;i<=num;i++) { ans+=dfs(bit-1,value-i*binary_index[bit],flag && (i==limit[bit]));///为什么不用dp[bit][value]递推的原因就是有范围限制，如果这次更新了，那么下次还是不能直接用 } if(!flag)///关键的地方，如果没有这一步的话，那么每一个都没有记录，时间复杂度一样 dp[bit][value]=ans; return ans;}int main(){ int nCase; scanf("%d",&nCase); index_init(); for(int t=1;t<=nCase;t++) { scanf("%I64d%I64d",&A,&B); init(); printf("Case #%d: %d\n",t,dfs(cnt-1,lvalue,1)); } return 0;}