P2602 [ZJOI2010]数字计数

https://www.luogu.org/problemnew/show/P2602

数位dp

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 const double minv=1e-;

 ll g[],shi[];

 void cal(ll a,ll c,int ori)

 {

     int i,w,s;

     w=(log(a+minv)/log());

     i=w;

     while (i>=)

         g[]-=shi[i--]*c;

     while (w>=)

     {

         s=a/shi[w];

         if (w!=)

             for (i=;i<;i++)

                 g[i]+=s*shi[w-]*w*c;

         for (i=;i<s;i++)

             g[i]+=shi[w]*c;

         g[s]+=(a%shi[w]+)*c;

         a=a%shi[w];

         w--;

     }

 }

 int main()

 {

     ll a,b;

     int i;

     scanf("%lld%lld",&a,&b);

     shi[]=;

     for (i=;i<=;i++)

         shi[i]=shi[i-]*;

     cal(b,,);

     cal(a-,-,);

     for (i=;i<;i++)

     {

         printf("%lld",g[i]);

         if (i!=)

             printf(" ");

     }

     return ;

 }

 /*

 1 999

 5 10

 10 20

 10 19

 1 1000000000000

 99 1000000000000

 */

 /*

 13 99

 8 15 18 19 19 19 19 19 19 19

 13 550

 104 210 213 214 214 156 104 104 104 104

 2 110

 21 32 21 21 21 21 21 21 21 21

 1 100000000

 68888897 80000001 80000000 80000000 80000000 80000000 80000000 80000000 80000000 80000000

 */

验证

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define minv 1e-6

 #define inf 1e9

 #define pi 3.1415926536

 #define nl 2.7182818284

 const ll mod=1e9+;//

 const int maxn=1e5+;

 ll g[];

 int main()

 {

     int i,j;

     ll a,b;

     scanf("%lld%lld",&a,&b);

     for (i=a;i<=b;i++)

     {

         j=i;

         while (j)

         {

             g[j%]++;

             j/=;

         }

     }

     for (i=;i<;i++)

         printf("%lld ",g[i]);

     return ;

 }

 /*

 13 99

 8 15 18 19 19 19 19 19 19 19

 13 550

 104 210 213 214 214 156 104 104 104 104

 2 110

 21 32 21 21 21 21 21 21 21 21

 1 100000000

 68888897 80000001 80000000 80000000 80000000 80000000 80000000 80000000 80000000 80000000

 */