题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4734
题意:就是给一个函数 <nobr aria&#45;hidden="true"> f(x) </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> x </mi> <mo stretchy="false"> ) </mo> </math> 原来的十进制变成二进制,但是系数不变,最后得到的十进制数

数位 <nobr aria&#45;hidden="true"> dp </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> d </mi> <mi> p </mi> </math>是上次寒假集训学的,没怎么学会。。。现在才来补
这道题的记录的状态有点特别,是记录枚举到这一位的和与 <nobr aria&#45;hidden="true"> f(A) </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math> 的差值,大于 <nobr aria&#45;hidden="true"> f(A) </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math> 的直接就不要了
按照哪位大佬的说法,我们正常来写的话,就应该是记录现在的 <nobr aria&#45;hidden="true"> sum </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> s </mi> <mi> u </mi> <mi> m </mi> </math>,以及每次的 <nobr aria&#45;hidden="true"> f(A) </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math>,然后来比较进行取舍,但是每个 <nobr aria&#45;hidden="true"> pos </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> p </mi> <mi> o </mi> <mi> s </mi> </math> <nobr aria&#45;hidden="true"> sum </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> s </mi> <mi> u </mi> <mi> m </mi> </math>不同吧,而且每次询问的 <nobr aria&#45;hidden="true"> f(A) </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math> 也不同,哇~那就要把这两种状态都记录下来,内存根本装不下,然后就想到记录两个的差值,真是太 <nobr aria&#45;hidden="true"> TM </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> T </mi> <mi> M </mi> </math> 的机智了~

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) ((long long)fac[(n)]*inv[(m)]%MOD*inv[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int tot,a[20];
map<int,int>dp[20];
LL f(LL x)
{
    if(x==0)return 0;
    LL ans=f(x/10);
    return (ans<<1)+x%10;
}
LL dfs(int pos,int sum,bool lim)
{
    if(sum>tot)return 0;                //大于f(A)的直接就不要了 
    if(pos==-1)return 1;
    if(lim==0&&dp[pos][tot-sum])return dp[pos][tot-sum];
    int up=lim?a[pos]:9;
    LL cnt=0;
    for(int i=0;i<=up;i++)
    {
        cnt+=dfs(pos-1,sum+i*(1<<pos),lim&&i==up);
    }
    if(lim==0)dp[pos][tot-sum]=cnt;     //以差值作为记录的状态 
    return cnt;
}
LL solve(LL n)
{
    int pos=-1;
    while(n)
    {
        a[++pos]=n%10;
        n/=10;
    }
    return dfs(pos,0,true);
}
int main()
{
    int T;
    cin>>T;
    for(int Case=1;Case<=T;Case++)
    {
        int A,B;
        cin>>A>>B;
        tot=f(A);
        cout<<"Case #"<<Case<<": "<<solve(B)<<endl;
    }
}