Bzoj 1833

coc youyl posted @ 2015年6月27日 20:15 in bzoj , 621 阅读

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1833

题目分类：乱搞

题意：

球在a-b的整数中每一个数码的出现次数

题解：

强行每一位推出1-9的出现次数，减出0出现的次数。

程序：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
long long d1[20][10];
long long n,m;
inline long long exp(long long x,long long y)
{
    long long ans=1;
    while (y!=0)
    {
        if(y&1)
        {
            y--;
            ans=(ans*x);
        }
        else
        {
            y/=2;
            x=x*x;
        }
    }return ans;
}
inline long long getdigit(long long x)
{
    long long ans=1;
    for (int i=1;i<=12;i++)
    {
        if(x>=exp(10,i))
        {
            ans+=exp(10,i-1)*9LL*i;
        //  printf("%d %d\n",i,ans);
        }
        else
        {
            ans+=(x-exp(10,i-1)+1)*i;
        //  printf("%d %d\n",i,ans);
            break;
        }
    }
    return ans;
}
long long s1[10],s2[10];
long long va[10];
inline void solve1(long long x)
{
    s1[0]=getdigit(x);
    if(x==0)
    {
        s1[0]=1;
        return;
    }
    int tp=0;
    while (x!=0)
    {
        tp++;
        va[tp]=x%10;
    //  printf("%d %I64d\n",tp,va[tp]);
        x/=10;
    }
//  printf("%d %I64d %I64d\n",tp,va[1],va[2]);
    long long val=0;
    if(va[1]!=0)s1[va[1]]++;
    for (int i=1;i<=tp;i++)
    {
        val+=va[i]*exp(10,i-1);
        if(i!=tp&&va[i+1]!=0)s1[va[i+1]]+=(val+1);
        for (int j=1;j<=9;j++)
        {
            s1[j]+=va[i]*d1[i-1][j];
        }
        for (int j=1;j<va[i];j++)
        {
            s1[j]+=exp(10,i-1);
        }
    }
    for (int i=1;i<=9;i++)s1[0]-=s1[i];
}
inline void solve2(long long x)
{
    s2[0]=getdigit(x);//printf("%d\n",s2[0]);
    memset(va,0,sizeof(va));
    if(x==0)
    {
        s2[0]=1;
        return;
    }
    int tp=0;
    while (x!=0)
    {
        tp++;
        va[tp]=x%10;
    //  printf("%d %I64d\n",tp,va[tp]);
        x/=10;
    }
//  printf("%d %I64d %I64d\n",tp,va[1],va[2]);
    long long val=0;
    if(va[1]!=0)s2[va[1]]++;
    for (int i=1;i<=tp;i++)
    {
        val+=va[i]*exp(10,i-1);//printf("%d\n",val);
        if(i!=tp&&va[i+1]!=0)s2[va[i+1]]+=(val+1);
        for (int j=1;j<=9;j++)
        {
            s2[j]+=va[i]*d1[i-1][j];
        }
        for (int j=1;j<va[i];j++)
        {
            s2[j]+=exp(10,i-1);
        }//printf("%d:",i);
    //  for (int j=1;j<=9;j++)
    //  {
    //      printf("%d ",s2[j]);
    //  }printf("\n");
    }
    for (int i=1;i<=9;i++)s2[0]-=s2[i];
//  printf("%d\n",s2[0]);
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for (int i=0;i<=9;i++)
    {
        d1[1][i]=1;
    }
    for (int i=2;i<=12;i++)
    {
        for (int j=0;j<=9;j++)
        {
            d1[i][j]=d1[i-1][j]*10LL+exp(10,i-1);//printf("%d %d %I64d\n",i,j,d1[i][j]);
        }
    }
    solve1(n-1);
    solve2(m);
    for (int i=0;i<=9;i++)
    {
        printf("%lld",s2[i]-s1[i]);
        if(i!=9)printf(" ");
    }
    return 0;
}