数位DP
枫林晚
2018-03-12 20:13:11
2018年3月12日20:00:55
基本思想在于将一个数拆分成每一位的数字，将总问题转化为子问题。
例：求[a,b]中各个数字出现次数。
（luogu2602 数字计数）
1.发现在i位数中（不考虑前导零），每一个数字出现的次数都相同。f[i]=f[i-1]*10+10^(i-1);
2.在ABCD中，将其拆为：A000+B00+C0+D;
A000中，考虑后三位每个数字出现次数都为：A*f[3];
3.再加上第一位上小于A(从零开始，算前导零的时候会减去）的数出现了10^3次
4.然而，后面的000~BCD中，每一个数的产生也伴随着A的一次出现，所以A出现次数单独加上BCD*1；
5.处理前导零；
仅在开始填0~9999（len-1个）时会产生。
零的数量单独减去10^（len-1）+10^(len-2)+...+10+1;
不用写两个query，
对于数组，传一个*就好。
详见代码：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=20;
ll a,b;
ll cnta[20],cntb[20];
ll f[20],ten[20];
void query(ll x,ll *cnt)
{
int len=0;
int num[20];
ll k=x;
while(k)
{
num[++len]=k%10;
k/=10;
}
for(int i=len;i>=1;i--)
{
for(int j=0;j<=9;j++)
cnt[j]=cnt[j]+f[i-1]*num[i];
for(int j=0;j<num[i];j++)
cnt[j]+=ten[i-1];
ll num2=0;
for(int j=i-1;j>=1;j--)
{
num2=num2*10+num[j];
}
num2++;
cnt[num[i]]+=num2;
cnt[0]-=ten[i-1];
}
}
int main()
{
scanf("%lld%lld",&a,&b);
ten[0]=1;
for(int i=1;i<=15;i++)
{
f[i]=f[i-1]*10+ten[i-1];
ten[i]=ten[i-1]*10;
}
query(a-1,cnta);
query(b,cntb);
for(int i=0;i<=9;i++)
printf("%lld ",cntb[i]-cnta[i]);
return 0;
}
```
luogu（P2602）