Solution

一道比较好的dp题 想了半天组合数QAQ

首先要知道的是 A<B一定是B有一位是1且A的这位是0且前面都相等

那么肯定是要枚举这一位在哪里然后求出方案数

方案数考虑类似背包的方法分三种情况转移具体见代码

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define F(i,a,b) for(register int i=(a);i<=(b);i++)using namespace std;typedef long long LL;const int N=5000,MOD=1e9+7;int n,m;LL ans,f[2][N][2];int main() {    cin>>n>>m;    for(int i=0;(1<
         
          <=max(n,m);i++) { memset(f,0,sizeof(f)); f[0][0][0]=1; for(int j=1;j<=max(n,m);j++) { int x=(j>>i)&1,c=j&1; for(int k=0;k<=2048;k++) F(X,0,1) { f[c][k][X]=f[c^1][k][X]; if(j<=n) f[c][k][X]=(f[c][k][X]+f[c^1][k^j][X])%MOD; if(j<=m) f[c][k][X]=(f[c][k][X]+f[c^1][k^j][X^x])%MOD; } } F(j,(1<
          
           <<(i+1))-1) ans=(ans+f[(max(n,m)&1)][j][1])%MOD; } printf("%lld",ans%MOD); return 0;}