[ZJOI2010]count 数字计数
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
好累...我真的再也不想做数位DP了...
啊，要统计[l,r]以内0~9出现的次数，减一减然后这道题就变成了求(0,k)以内各个数位出现的次数
[1,9]都是一样的，0比较特(e)殊(xin),一会儿再说，先说怎么处理[1,9]的情况
先假设当前要处理的数位为j(1 <= j <= 9)，可以DP得到f[i][j]为i位以内(即(0,10^i)以内)j出现的次数
然后就是讨论3种情况:
(设k十进制共l位，从低到高第p位为b(p))
①首位为0 (f[l - 1][j])
②首位为[1,b(l) - 1] ((b(l) - 1) * f[l - 1[j] ,若b(l) >= j则再加上10^(l - 1))
③首位为b(l),这个情况比较复杂，不过仔细思考一下还是能得出的（具体的看代码吧..)
然后是待求数位为0的情况，首先需要维护两个数组:f[i][0]和h[i],其中f[i][0]的含义和前面一样，h[i]表示算上前缀0，刚好i位的数中0出现次数，这两个都可以DP求（吧...）(反正我是用组合求的...)
然后还是讨论上面三种情况，公式基本不变(还是有些变动，不过都是很好推的，具体看代码吧...)，但是有些地方f[i][j]要换成h[i]
注意有些地方区间的开闭，还有精度啊啥啥的，基本上这道题就可以A了...
完整代码如下：
#include <stdio.h>
#include <iostream>
#include <string.h>
typedef long long Long;
Long f[20][20];
Long h[20][1];
Long p[20];
Long pow(Long a,int b)
{
int m = (1 << 30);
Long r = 1LL;
while(m)
{
r *= r;
if(m & b)
r *= a;
m >>= 1;
}
return r;
}
Long yh[100][100];
Long C(int a,int b)
{
if(yh[a][b])
return yh[a][b];
if(b == 0 || b == a)
return yh[a][b] = 1LL;
if(b > a)
return 0LL;
return yh[a][b] = C(a - 1,b) + C(a - 1,b - 1);
}
void init()
{
for(int j = 1;j < 10;j++)
{
f[1][j] = 1;
}
Long e = 1;
for(int i = 2;i < 20;i++)
{
e *= 10;
for(int j = 1;j < 10;j++)
{
f[i][j] = e + 10 * f[i - 1][j];
}
}
h[1][0] = 1;
//f[1][0] = 1;
for(int i = 2;i < 20;i++)//要！算！前！导！零！！！
{
f[i][0] += f[i - 1][0];
for(int j = 1;j <= i;j++)
{
h[i][0] += j * pow(9,i - j) * C(i,j);
if(j <= i - 1)
f[i][0] += j * pow(9,i - j) * C(i - 1,j);
}
// std::cerr<<i<<" (f) "<<f[i][0]<<std::endl;
// std::cerr<<i<<" (h) "<<h[i][0]<<std::endl;
// std::cerr<<i<<" (hs) "<<hs[i][0]<<std::endl;
}
}
int len = 0;
int bit[20];
Long get_res_0(Long k)
{
memset(bit,0,sizeof(bit));
len = 0;
Long q = k;
while(q)
{
bit[++len] = q % 10;
q /= 10;
}
Long result = 0LL;
result += f[len - 1][0];
result += 1LL * (bit[len] - 1) * h[len - 1][0];
Long T = 0;
for(int i = len - 1;i >= 1;i--)
{
if(bit[i + 1] == 0)
T ++;
for(int p = 0;p < bit[i];p++)
{
result += T * pow(10,i - 1);
result += h[i - 1][0];
if(p == 0)
result += pow(10,i - 1);
}
}
return result;
}
Long get_res(Long k,int j)
{
/*
if(k < 10)
{
if(k > j)
return 1;
return 0;
}
*/
if(j == 0)
return get_res_0(k);
memset(bit,0,sizeof(bit));
len = 0;
Long q = k;
while(q)
{
bit[++len] = q % 10;
q /= 10;
}
Long result = 0LL;
result += f[len - 1][j];
result += 1LL * (bit[len] - 1) * f[len - 1][j] + (j <= (bit[len] - 1) ? (pow(10,len - 1)) : 0);
Long T = 0;
for(int i = len - 1;i >= 1;i--)
{
if(bit[i + 1] == j)
T ++;
for(int p = 0;p < bit[i];p++)
{
result += T * pow(10,i - 1);
result += f[i - 1][j];
if(p == j)
result += pow(10,i - 1);
}
}
return result;
}
int main()
{
init();
Long a = 0;
Long b = 0;
std::cin>>a>>b;
Long res = 0;
for(int i = 0;i < 10;i++)
{
res = get_res(b + 1,i) - get_res(a,i);
/*
if(i == 0)
{
if(a == 0)
res ++;
}
*/
if(i != 9)
std::cout<<res<<" ";
else std::cout<<res<<std::endl;
}
return 0;
}
评论 (0)
