[bzoj 1662--Usaco2006 Nov]Round Numbers 圓環數

正如你所知，奶牛們沒有手指以至于不能玩“石頭剪刀布”來任意地決定例如誰先擠奶的順序。她們甚至也不能通過仍硬币的方式。

是以她們通過”round number”競賽的方式。第一頭牛選取一個整數，小于20億。第二頭牛也這樣選取一個整數。如果這兩個數都是”round numbers”，那麼第一頭牛獲勝，否則第二頭牛獲勝。

如果一個正整數N的二進制表示中，0的個數大于或等于1的個數，那麼N就被稱為 “round number” 。例如，整數9，二進制表示是1001，1001 有兩個’0’和兩個’1’; 是以，9是一個round number。26 的二進制表示是11010 ; 由于它有2個’0’和 3個’1’，是以它不是round number。

很明顯，奶牛們會花費很大精力去轉換進制，進而确定誰是勝者。 Bessie 想要作弊，而且認為隻要她能夠知道在一個指定區間範圍内的”round numbers”個數。 幫助她寫一個程式，能夠告訴她在一個閉區間中有多少Hround numbers。區間是 [start,finish]，包含這兩個數。 (1 <= Start < Finish <= 2,000,000,000)

這道題的題解千奇百怪，那麼我來講一下記憶化搜尋版本的數位dp。首先需要把一個數轉化為二進制，可用取mod的方法（然而身為蒟蒻的我一下子沒想到，用了非常醜的方法），之後呢，定一個三維的dp，f[i][j][k]，i表示枚舉到第i位（從後往前），j為枚舉到現在的0的個數，k則為枚舉到現在的1的個數，然後就跟十進制的做法一樣，記得要判斷前導0，記得dfs要判斷return 0的情況，不然會錯得很慘。（來自一個蒟蒻的忠告）

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int a[],b[],mi[];
long long f[][][];
long long dfs(int pos,int n0,int n1,bool lead,bool limt)
{
    if(pos==)
    {
        if(n0>=n1)return ;
        return ;
    }
    if(lead==false && limt==false && f[pos][n0][n1]!=-)return f[pos][n0][n1];
    int up=,ans=;
    if(limt==true)up=a[pos];
    for(int i=;i<=up;i++)
    {
        int he1=n0,he2=n1;bool bk1=false,bk2=false;
        if(i== && lead==false)he1++;
        if(i==)he2++;
        if(i== && lead==true)bk1=true;
        if(limt==true && i==a[pos])bk2=true;
        ans+=dfs(pos-,he1,he2,bk1,bk2);
    }
    if(lead==false && limt==false)f[pos][n0][n1]=ans;
    return ans;
}
long long solve(int x)
{
    int pos=,ss=;
    bool bk=true;
    while(x)
    {
        if(x>=mi[ss])
        {
            b[++pos]=;
            x-=mi[ss];
            bk=false;
        }
        else
        {
            if(bk==false)b[++pos]=;
        }
        ss--;
    }    
    ss++;
    while(ss--)b[++pos]=;
    for(int i=;i<=pos;i++)a[i]=b[pos-i+];
    return dfs(pos,,,true,true);
}
int main()
{    
    int n,m;
    scanf("%d%d",&n,&m);
    mi[]=;
    for(int i=;i<=;i++)mi[i]=mi[i-]*;
    memset(f,-,sizeof(f));
    printf("%lld\n",solve(m)-solve(n-));
    return ;
}