[数位DP][组合数学][整数分段] UVa 11038 How Many O’s?

自己写了个有点繁杂的数位dp，本来一发过还有点高兴，但是看了前排dalao代码发现自己写的太复杂了。。。。这个题其实只用组合数学就可以解emmmm

先上自己的屌丝做法：分段dp，从前往后，组合数学算下可以知道能预处理出来一段长度为n的可以包含前导0的数据的所有0的个数，我本来想的是用f(p,m,isf)表示当前是第p个数字，最大为m然后是否为上限isf表示状态，但是写着写着发现不用这么来。。。。所以其实到最后程序里的isf就没有用（在发现这一点的时候我就该想到其实不用这么“dp“），把当前位为0特判一下加上后面的所有可能数字（这个也可以预处理），算完当前这一位之后往下一位继续算。。。最后由于我在f里面的枚举都是从0开始，所以等于说算出来的是”可以包含前导0的数的0的个数“，所以在cal里面还要减去所有的前导0的个数。。。麻烦一批

再说dalao们的做法：其实这个前导0的问题很容易解决。。。从后往前算就ok了，每次算到一位的时候判断是不是0，不是0的话，可以想到当前位为0的话总共出现的次数是容易计算的：把整个数字从这个点分开成左右两段（不包括当前这一位），那么左边的数字*10^(右边的位数),如果当前为0那就不能这么算了（跟数位dp一个道理，isf的时候不能当成所有的情况来做）,但是仍然很简单：只要左边不是最大的那个数字，右边仍然可以取到所以情况，所以这时候把左边-1乘上右边的10幂，再加上右边所有的本身的上限就行了。。。还是看代码比较好说。

我自己的代码

#include

using namespace std;

typedef long long LL;
const int maxn=2e4+5;

int n,dig[20];
LL p10[30],p9[30],dp[30][20],fc[20],pt[30];
long long C[2070][2070];
void get_C()//注意MOD相减可能会产生负数
{
    int m=15;
    C[0][0] = 1;
    for(int i=1;i<=m;i++)
    {
        C[i][0] = 1;
        for(int j=1;j<=i;j++)
            C[i][j] = C[i-1][j]+C[i-1][j-1];
    }
}
void pre()
{
    p10[0]=p9[0]=1;
    for(int i=1;i<=20;i++)
        p10[i]=10*p10[i-1],p9[i]=p9[i-1]*9;
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=i;j++)
        {
            pt[i]+=1LL*j*p9[i-j]*C[i][j];
        }
    }
    return ;
}
LL f(int p,int m,int isf)
{
    if(p==1)return 1;
    if(!isf&&dp[p][m]!=-1LL)//记忆化
        return dp[p][m];

    int up=isf?m-1:9;
    LL ret=0;
    if(up>=0)
        ret+=p10[p-1];//for cur's 0

    for(int i=0;i<=up;i++)
        ret+=pt[p-1];//当前为i，后面任意，所有的情况的所有0


    if(isf)
    {
        if(m==0)
            ret+=fc[p-1]+1;//当前最大的为0，这个应该加上之后所有的可能的情况

        ret+=f(p-1,dig[p-1],1);//下一个数字
    }
    if(!isf)
        dp[p][m]=ret;//记忆化
    return ret;
}

LL cal(LL a)
{
    if(a<0)
        return 0;
    if(a<10)
        return 1;
    memset(dp,-1LL,sizeof(dp));
    n=0;

    while(a)
    {
        dig[++n]=a%10;
        a/=10;
    }
    LL ten=1;

    for(int i=1;i<=n;i++)
    {
        fc[i]=fc[i-1]+ten*dig[i];
        ten*=10;
    }

    LL ans=f(n,dig[n],1);

    for(int i=1;i<=n;i++)//减去前导0的数量，每个0算了10^i次
        ans-=(p10[n-i]);

    return ans+1;
}

int main()
{
    LL a,b;
    get_C();
    pre();
    while(~scanf("%lld%lld",&a,&b)&&a>=0)
    {
        cout<
 
dalao代码
#include

using namespace std;

typedef long long LL;
const int maxn=2e4+5;
LL n,m;
LL cal(LL x)
{
    if(x<0)
        return 0;
    LL ans=1,cnt=1,tmp=0;
    while(x)
    {
        LL cur=x%10;
        x/=10;
        if(cur)
            ans+=x*cnt;
        else
            ans+=(x-1)*cnt+tmp+1;
        tmp+=cur*cnt;
        cnt*=10;
    }
    return ans;
}

int main()
{
    while(~scanf("%lld%lld",&n,&m)&&n!=-1&&m!=-1)
        printf("%lld\n",cal(m)-cal(n-1));
    return 0;
}