Codeforces 258B Little Elephant and Election 4/10

非常經典的一個題目

重點在他的第一個部分：

給一個  有N位 的數字 M，問1~M

有1個4 or 7的有幾個

有2個4 or 7的有幾個

有3個4 or 7的有幾個

…

這樣。

比較好的作法應該是

從最高位開始，從那位以前都一樣

但枚舉那一位的大小（小於原本的值）

再去枚舉剩下的位置有幾個4

最後再用nCm去計算～

這樣編程複雜度低，時間複雜度也很低

scanf("%d", &m), m++, cnt[0]--;

while(m) a[++n] = m % 10, m /= 10;

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

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

        C[i][j] = i && j? (C[i-1][j-1]+C[i-1][j]) % M: 1;

for (int i = n; i; i--){

    for (int j = 0; j < a[i]; j++){

        LL now = 1LL << i-1;

        for (int k = i-1; k >= 0; k--){

            cnt[prv+(j == 4 || j == 7)+k] += now * C[i-1][k];

            now *= 8/2;

        }

    }

    prv += (a[i] == 4 || a[i] == 7);

}