poj-3286

//stupid method!!!!!!!!!!!!!!!
//388K  360MS   G++
#include <stdio.h>
#include <string.h>
#include <math.h>

int C[33][33]; // C[n][m], choose m from n;

void getCombination() {
    for (int n = 0; n <= 32; n++) {
        for (int m = 0; m <= n; m++) {
            if (m == 0) { // choose nothing
                C[n][m] = 1;
            } else if (n == 0) { // nothing to choose
                C[n][m] = 0;
            } else if (m > n) {
                C[n][m] = 0;
            } else if (m == n) {
                C[n][m] = 1;
            } else {
                C[n][m] = C[n-1][m] + C[n-1][m-1];
                // printf("C %d %d is %d\n",n, m, C[n][m]);
            }
        }
    }
}

char str1[20];
char str2[20];

int getHowManyZero(char * num) {
    int zeroNum = 0;
    int length = strlen(num);
    for (int i = 0; i < length; i++) {
        if (num[i] == '0') {
            zeroNum++;
        }
    }
    return zeroNum;
}

long long getZeroNum(char * num) {
    int length = strlen(num);
    long long totalZeroNum = 1; // 0 has 1 '0'

    // step 1, all value's length < num
    for (int curLength = 1; curLength <= length-1; curLength++) {
        for (int zeroNum = 1; zeroNum <= curLength - 1; zeroNum++) {
            totalZeroNum += zeroNum*
                        C[curLength - 1][zeroNum]*pow(9, curLength - zeroNum);
        }
    }

    // printf("S1 %lld\n", totalZeroNum);

    //step2, all value's length == num's length, first pos val < num's first pos val
    char firstChar = num[0];
    int possibleMostChoose = firstChar - '1';
    if (possibleMostChoose > 0) {
        long long curTotalNum = 0;
        for (int zeroNum = 1; zeroNum <= length-1; zeroNum++) {
            curTotalNum += zeroNum*C[length-1][zeroNum]
                            *pow(9, length-1 - zeroNum);
        }
        totalZeroNum += possibleMostChoose * curTotalNum;
    }

    // printf("S2 %lld\n", totalZeroNum);

    int beforeZeroNum = 0;
    for (int curPos = 1; curPos <= length-1; curPos++) { // from the 2nd char to last char
        char curChar = num[curPos];
        int possibleMostChoose = curChar - '0';

        if (possibleMostChoose > 0) {
            long long curTotalNum = 0;
            if (possibleMostChoose-1 > 0) {            
                for (int zeroNum = 0; zeroNum <= length - curPos -1; zeroNum++) {
                    curTotalNum += (zeroNum + beforeZeroNum)*C[length - curPos -1][zeroNum]
                                *pow(9, length - curPos - 1 - zeroNum);
                }
                totalZeroNum += (possibleMostChoose-1) * curTotalNum;
            }
            
            // for '0'
            curTotalNum = 0;
            if (length - curPos -1 >= 1) {            
                for (int zeroNum = 0; zeroNum <= length - curPos -1; zeroNum++) {
                    curTotalNum += (zeroNum + 1 + beforeZeroNum)*C[length - curPos -1][zeroNum]
                                *pow(9, length - curPos - 1 - zeroNum);
                }
            } else { // last pos
                // curTotalNum +=  (possibleMostChoose-1) * beforeZeroNum;
                curTotalNum += (beforeZeroNum + 1);            
            }
            totalZeroNum += curTotalNum;

        } else if (possibleMostChoose == 0) {
            beforeZeroNum++;
        }
    }

    // printf("S3 %lld\n", totalZeroNum);

    return totalZeroNum;
}

int main() {
    getCombination();
    while(scanf("%s %s", str1, str2) != EOF) {
        // printf("%s %s\n", str1, str2);
        if (str1[0] == '-') {
            return 0;
        }
        long long nZeroNum = getZeroNum(str2);
        int zeroNumEnd = getHowManyZero(str2);
        if (str1[0] != '0') {
            long long mZeroNum = getZeroNum(str1);
            printf("%lld\n", nZeroNum - mZeroNum + zeroNumEnd);
        } else {
            printf("%lld\n", nZeroNum + zeroNumEnd); 
        }
    }
}

用了非常笨的办法来得到0的个数，是从排列组合的角度出发， 对当前数字的每一位进行检查，遍历比起小并且含有0的数，累加0的个数，但是这种朴素的思路会有很多特殊情况，到最后完全就是一堆逻辑的堆砌，十分难看，贴一个容易理解的别人的题解：

From:javascript:void(0)

首先转化成求 [0, x] 中所有数中，含有的 0 的个数

那么对于一个数 x，怎么求出从 0 到 x 中所有数含有 0 的个数的和呢？

我们可以限制每一位是 0，然后再来计算。举个例子，假设 x 是 21035

        首先 0 肯定是一个，sum 赋初值为 1

        个位数是 0

                个位数前面的数不能是 0，能够取的数就是 [1, 2103]，个位后面没有了

                那么 sum+=2103*1

        十位数是 0

                十位数前面的数不能是 0，能够取的数就是 [1, 210]，由于 0 比 3 小，十位后面可以取 [0, 9]

                那么 sum+=210*10

        百位数是 0

                百位数前面的数不能是 0，能够取的数就是 [1, 21]，由于 0 是等于 0 的，这里就要特殊处理下了：

                百位数前面的数如果是在 [1, 20] 中的，百位数后面的数可以取的就是 [0, 99]

                百位数前面的数如果取的是 21，百位数后面的数就只能取 [0, 35]

                那么，sum+=20*100+36

        ......

相信手推到这里了，读者已经能够明白怎么操作

这种思路 细化到每个位，取0时，能够得到的比数N小的数的个数（也就是该位0的个数），然后利用加法原理进行累加，逻辑比较简明，但是还是有特殊情况处理的.

比如算4123中有多少个2

按位统计,,,先算各位,,个位是2的情况有413种,,,因为各位左边可以0~412,,,而右边没有数字,,,

然后是十位,,,十位是2的有41*10 + 1*4种,,当左边从0~40时,,,右边可以从0~9,,,而左边为41时,,右边只能从0~3

然后是百位,,,,百位有4*100种,,,,即左边从0~3,,右边从0~99

千位有  1*1000,,,左边没有数字,,,右边0~999,,,,

上面是计算1~9,,,,计算0的时候比较特殊,,,,原因是除了0这一个数字之外,,,,0不能做开头,,,

可以看到在求1~9的个数的时候,,,都是分为2部分相乘,,,这样0的处理也很简单,,只需把相乘的左半部分-1,,,,