bzoj 1833: [ZJOI2010]count 数字计数【数位dp】

非典型数位dp

先预处理出f[i][j][k]表示从后往前第i位为j时k的个数，然后把答案转换为ans(r)-ans(l-1)，用预处理出的f数组dp出f即可（可能也不是dp吧……）

#include<iostream>

#include<cstdio>

using namespace std;

long long l,r,t[25];

struct dp

{

    long long a[15];

    dp operator + (dp x)

    {

        dp r;

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

			r.a[i]=a[i]+x.a[i];

        return r;

    }

}f[20][20];

dp work(long long x)

{

    dp ans;

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

		ans.a[i]=0;

    if(!x)

    {

        ans.a[0]=1;

        return ans;

    }

    int len=15;

    while(t[len]>x)

		len--;

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

		for(int j=1;j<=9;j++)

			ans=ans+f[i][j];

    ans.a[0]++;

    int cur=x/t[len];

    for(int i=1;i<cur;i++)

		ans=ans+f[len][i];

    x%=t[len];

    ans.a[cur]+=x+1;

 	for(int i=len-1;i;i--)

    {

        cur=x/t[i];

        for(int j=0;j<cur;j++)

			ans=ans+f[i][j];

        x%=t[i];

        ans.a[cur]+=x+1;

    }

    return ans;

}

int main()

{

    t[1]=1;

    for(int i=2;i<=15;i++)

		t[i]=t[i-1]*10;

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

		f[1][i].a[i]=1;

    for(int i=2;i<=12;i++)

		for(int j=0;j<=9;j++)

			for(int k=0;k<=9;k++)

			{

				f[i][k]=f[i][k]+f[i-1][j];

				f[i][k].a[k]+=t[i-1];

			}

    scanf("%lld%lld",&l,&r);

    dp ans1=work(r),ans2=work(l-1);//cout<<"aa";

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

		printf("%lld ",ans1.a[i]-ans2.a[i]);

    return 0;

}

巴特西

bzoj 1833: [ZJOI2010]count 数字计数【数位dp】

最新文章

热门文章