牛客小白月赛31A

这比赛我直接被开幕雷击
开局A题放一个数位DP是我没有想到的
没错！这道题是一道数位dP板子题！
（但是我用的记忆化搜索实现）

我们要满足 a∣b==a+b
就需要满足 a&b==0
我们就可以知道 b 的二进制下，哪些位数可以为1
b 还需要满足 1≤b≤x ，用数位DP计算即可
计算结束后，由于数位DP将b==0也统计进了答案，所以答案减1

参考程序

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,x;
int len;
int a[1000];
int dp[1000];
int dfs(int x,int eq)
{
    if(!eq&&dp[x]) return dp[x];
    if(!x) return 1;
    int h=eq?a[x]:1,ans=0;
    if(h&& ((k>>(x-1))&1)==0 ){
        ans+=dfs(x-1,eq&&(h==a[x]));
    }

    ans+=dfs(x-1,eq&&(0==a[x]));
    if(!eq) dp[x]=ans;
    return ans;
}
void work()
{
    cin>>k>>x;
    len=0;
    while(x){
        a[++len]=x%2;
        x/=2;
    }
    cout<<dfs(len,1)-1<<"\n";
    memset(dp,0,sizeof(dp));
}
int T;
signed main()
{
    cin>>T;
    while(T--) work();
    return 0;
}