F(x)

思路：
这个数位卡我时间又卡我空间，时间和空间限制都很小，时间就500ms。

我想通过再开一个数组记录访问过的状态是否与本次输入有关，来避免每次都要初始化数组，同时又不用多开一维（会爆空间，），即便如此还是会超时，因为它有组数据，所以如果每次都重新算一遍的话，铁定超时，与是否初始化的时间开销无关。

然后参考了一位博主的博客，我数位白学了。

对于我解这题固有的思路而言，"判断是否"并没有体现在的状态中，所以这样产生的值是依赖于的，仅能应用在当前数据上，如果数据量大就会。

但是完全可以采取更优的方案消除状态与输入的相关性。（无论你取什么值，都是一个常量，永远不会改变。）
以前也有过消除状态与输入的相关性，但都是模板刚好就能完成或者没有多组输入，而这题的第二维需要存储第位到最低位最多还能够增加的值，留意当状态与输入相关时怎么去消除这个性质。

我居然因为没有初始化卡了几十分钟，菜~

Code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int dp[11][4600];
int digit[11],all;
int dfs(int len,int sum,bool limit) {
    if(sum<0) return 0;
    if(!len) {
        return 1;
    }
    if(!limit&&dp[len][sum]!=-1) return dp[len][sum];
    int endi=(limit?digit[len]:9);
    int ans=0;
    for(int i=0;i<=endi;++i) {
        ans+=dfs(len-1,sum-i*(1<<(len-1)),limit&&i==endi);
    }
    if(!limit) dp[len][sum]=ans;
    return ans;
}
int solve(ll x) {
    int len=0;
    while(x) {
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,all,true);
}
void change(int n) {
    all=0;
    int tmp=1;
    while(n) {
        all+=(n%10)*tmp;
        tmp<<=1;
        n/=10;
    }
}
int main() {
    int t=read(),cas=0,r,n;
    memset(dp,-1,sizeof dp);
    while(t--) {
        cas+=1;
        n=read(),r=read();
        change(n);
        printf("Case #%d: %d\n",cas,solve(r));
    }
    return 0;
}