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
*/
上一篇:[国嵌笔记][020][ARM家族大检阅]


下一篇:WPF中RDLC报表的钻取实现