【P2602】【ZJOI2012】数字计数

传送门

Description

给定两个正整数\(a\)和\(b\)，求在\([a,b]\)中的所有整数中，每个数码(\(digit\))各出现了多少次。

Input

两个正整数\(a,b\)

Output

输出一行十个用空格隔开的整数，依次代表\(0~\sim~9\)出现了几次。

Hint

\(For~All:\)

\(1~\leq~a~\leq~b~\leq~1~\times~10^{12}\)

Solution

特别特别特别恶心的数位DP。

这里使用两个数字\(f,g\)代表到一个位置的答案和方案数。

设\(f_{i,0/1}\)为从高到低填到第\(i\)位，否/是顶上界的某一数码出现的次数。

\(g_{i,0/1}\)代表从高到低填到低\(i\)位，否/是顶上界的总共可能有多少个数。

转移十分细节。

对于不顶上界的，上一位不顶上界的下一位填什么都合法，所以有

\(f_{i,0}=f_{i-1,0}~\times~10\)

对于上一位不顶上界的方案，这一位填\(s_i\)显然合法，于是有

\(f_{i,0}=g_{i-1,0}\)

对于上一位顶上界的，这一位可以填\(0~\sim~s_i-1\)，于是有

\(f_{i,0}=f_{i-1,0}~\times~s_i\)

对于上一位顶上界的，这一位如果可以填这一位\(p\)，也是合法的

\(++f_{i,0}|s_i>p\)

诸如此类考虑之前所有位的答案在这一位产生的新数的贡献以及这一位放这个数的贡献即可。

#include<cstdio>

#include<cstring>

#define rg register

#define ci const int

#define cl const long long int

typedef long long int ll;

namespace IO {

    char buf[90];

}

template<typename T>

inline void qr(T &x) {

    char ch=getchar(),lst=' ';

    while(ch>'9'||ch<'0') lst=ch,ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

    if(lst=='-') x=-x;

}

template<typename T>

inline void write(T x,const char aft,const bool pt) {

    if(x<0) x=-x,putchar('-');

    int top=0;

    do {

        IO::buf[++top]=x%10+'0';

        x/=10;

    } while(x);

    while(top) putchar(IO::buf[top--]);

    if(pt) putchar(aft);

}

template<typename T>

inline T mmax(const T a,const T b) {if(a>b) return a;return b;}

template<typename T>

inline T mmin(const T a,const T b) {if(a<b) return a;return b;}

template<typename T>

inline T mabs(const T a) {if(a<0) return -a;return a;}

template<typename T>

inline void mswap(T &a,T &b) {

    T temp=a;a=b;b=temp;

}

const int maxn = 15;

ll a,b;

int st[maxn];

ll frog[maxn][3],gorf[maxn][3];

ll solve(ll,ci);

int main() {

	qr(a);qr(b);

	for(rg int i=0;i<9;++i) {

		write(solve(b,i)-solve(a-1,i),' ',true);

	}

	write(solve(b,9)-solve(a-1,9),'\n',true);

	return 0;

}

ll solve(ll x,ci p) {

	if(!x) return x;

	memset(frog,0,sizeof frog);

	memset(gorf,0,sizeof gorf);

	int len=0;rg ll dx=x;

	do {++len;} while(dx/=10);dx=x;

	for(rg int i=len;i;--i) st[i]=dx%10,dx/=10;

	gorf[1][0]=st[1]-1;gorf[1][1]=1;

	if(p&&p < st[1]) frog[1][0]=1;else if(p == st[1]) frog[1][1]=1;

	for(rg int i=1;i<len;++i) {

		rg int di=i+1;

		frog[di][0]=frog[i][0]*10+gorf[i][0]+frog[i][1]*st[di];

		frog[di][1]=frog[i][1];

		if(st[di] > p) ++frog[di][0];else if(st[di] == p) ++frog[di][1];

		if(p) ++frog[di][0];

		gorf[di][0]=gorf[i][0]*10+9+gorf[i][1]*st[di];

		gorf[di][1]=1;

	}

	return frog[len][0]+frog[len][1];

}

Summay

1、进行数位DP时，一共只有四种转移方向：

顶上界→填小于\(s_i\)→不顶上界

顶上界→填等于\(s_i\)→顶上界

不顶上界→填\(0~\sim~9\)→不顶上界

前导\(0\)→填\(1~\sim~9\)→不顶上界

2、可以通过记录方案数的辅助数组简化转移和复杂度。

巴特西