生若有余

兩個都是麻煩的計數(shù)問題,只不過一個是二進制,另一個似乎更貼近十進制的現(xiàn)實世界.不過計算機里,還是二進制感覺能跑得更快一些,移位總比乘十來得更快一些.
計數(shù)從0-n的每一位的數(shù)字個數(shù),先計數(shù)位數(shù)小于n的位數(shù)的數(shù)字個數(shù),再從高位到低位依次循環(huán)累加計數(shù)和n位數(shù)相同且小于n的數(shù)的各位數(shù)字.考慮的情形很多,有一點考慮不到就很難得到正確答案.

/**//*Source Code

Problem: 2282  User: y09shendazhi 
Memory: 220K  Time: 16MS 
Language: C++  Result: Accepted 

Source Code */
#include <iostream>
using namespace std;

int ans[15];//answer
int pow(int a,int b)
{
    int an=1;
    for(int i=0;i<b;i++)
        an*=a;
    return an;
}
void solve(int n)
{
    int i,j,k;
    memset(ans,0,sizeof(ans));
    if(n<10)
    {
        for(i=1;i<=n;i++)
            ans[i]=1;
        return ;
    }
    
    int digit[20]={0};
    int dec=0;//decimal of n
    int temp=0;
    temp=n;
    while(temp)
    {
        digit[dec++]=temp%10;
        temp/=10;
    }
    temp=pow(10,dec-1);

    for(i=1;i<10;i++)//位數(shù)小于n的
        ans[i]+=(dec-1)*temp/10;
    ans[0]+=(dec-1)*temp/10-(temp-1)/9;
    
    for(i=1;i<digit[dec-1];i++)//最高位是  1~最高位
    {
        ans[i]+=temp;
        for(k=0;k<10;k++)
            ans[k]+=(dec-1)*temp/10;
    }
    temp/=10;
    for(i=dec-2;i>=0;i--)
    {
        for(j=0;j<digit[i];j++)
        {
            for(k=dec-1;k>i;k--)
                ans[digit[k]]+=temp;
            ans[j]+=temp;
            for(k=0;k<10;k++)
                ans[k]+=i*temp/10;
        }
        temp/=10;
    }
    for(i=0;i<dec;i++)
        ans[digit[i]]++;
}
int main(int argc, char *argv[])
{
    int n,m;
    int ans1[15]={0};
    int temp=0;
    while(cin>>n>>m)
    {
        if(n==0 && m==0)
            break;
        if(n>m)
        {
            temp=n;
            n=m;
            m=temp;
        }
        solve(n-1);
        memcpy(ans1,ans,sizeof(ans));
        solve(m);
        for(int i=0;i<9;i++)
            cout<<ans[i]-ans1[i]<<' ';
        cout<<ans[9]-ans1[9]<<endl;
    }
    
    return 0;
}

/**//*Source Code

Problem: 3252  User: y09shendazhi 
Memory: 136K  Time: 0MS 
Language: C++  Result: Accepted 

Source Code */
#include <iostream>
using namespace std;

// /n\
// | |
// \m/
__int64 com(__int64 n ,__int64 m)
{
    if(n<m)
        return 0;
    __int64 result=1;
    m=m<n-m?m:n-m;
    for(__int64 i=1;i<=m;i++)
        result=(result*(n-m+i))/i;    
    return result;
}

__int64 sumCom(__int64 n,__int64 m)
{
    if(n==0 && m>=0)
        return 1;
    if(m>n)
        m=n;
    if(m<0)
        return 0;
    __int64 ans=0;
    for(__int64 i=0;i<=m;i++)
    {
        ans+=com(n,i);
    }
    return ans;
}

__int64 solve(__int64 n)
{
    if(n==0 || n==1)
        return 0;

    __int64 ans=0;
    __int64 dec=0;//二進制位數(shù)
    __int64 temp=n;
    while(temp)
    {
        dec++;
        temp>>=1;
    }
    temp=1;
    temp<<=dec-1;

    __int64 one=0;
    for(__int64 j=1;j<dec;j++)
            ans+=sumCom(j-1,j/2-1);
    temp>>=1;
    one++;
    for(__int64 i=dec-1;i>0;i--)
    {
        if(temp&n)
        {
            ans+=sumCom(i-1,dec/2-one);
            one++;
        }
        temp>>=1;
    }
    if(one<=dec/2)
        ans++;
    return ans;
}
int main()
{
    __int64 S,F;
scanf("%I64d%I64d",&S,&F);
    {
        if(S==0)
            printf("%I64d\n",solve(F));
        else
            printf("%I64d\n",solve(F)-solve(S-1));

    }
    return 0;
}