egin{align} 10^{i-1}+0.9 imes10^{i-1}+...+0.9^{i-1} imes10^{i-1}\ =frac{10^{i-1}(1-0.9^i)}{1-0.9}=10^i(1-0.9^i)\ =10^i-9^i end{align}">

也可以這麼理解，1個2都沒有的數，相當於每位只能從除掉2的9個數碼中選，顯然只能有 [公式] 個，於是小於 [公式] 且數碼含有2的數應該是 [公式] 個

這都是最基本的排列組合問題了。

我們要解決的不是題，而是思維方式。

n位數，固定其中的1位數，其他位數隨便取，自然是10∧（n-1）個數。那麼，挨個固定一下，就得到出現這個固定數的次數，當然就是n×10∧（n-1）個。

另一種想法是，從0到10∧n這n位數，理所當然的，每一位出現的任意數字的概率是平等的。神明沒有給予一個數字特殊的位置。

而這些數字一共有n×10 ∧n個。因此，其中一個數出現的次數，不用我說了吧，就是這個數字的十分之一。

為了讓數字平等，我們必須讓自然數從零開始，並在不一樣的位數前面補零。這似乎昭示了，不是人類發明瞭數學，而是神明創造了數學這和諧，完美的規則。

由於最大的數字一定不包含2，例如1000一定不包含，我們可以把最大的數字看作0。

這樣就是000-xxx，總共有10^i個數字，每一個數字會有i位，把他們都寫出來就有i*10^i位。

每一位都有可能是0-9十種可能，由於2不是特殊的，所以出現的2的個數是總數的1/10。

也就是總位數i*10^i的1/10，也就是：

i*10^(i-1)

以下是原回答，太複雜可以不看

==========================

如果是我做這道題目，大概會這麼做：

考慮i=2的情況，也就是x區間是1-100，是三位數。

第一位穩定為1，不可能是2

第二位是2時，第三位有十種可能的組合，也就是10個

第三位是2時，第二位有十種可能的組合，也就是10個

總數就是20個，包含了22這個出現2次，以及02這個特殊數字

也就是說，規律是，從第2位到第i+1位，總共i位，每一位固定為2時，其他i-1位有排列組合的數字個數10^(i-1)，舉例：

i=3時，2xx有，x2x和xx2各有100個，所以是3*100個（忽略1000這個四位數）

所以結論是:

i*10^(i-1)

好神奇，你都會變成了，這麼簡單的問題想不明白？

命題：0~10^n的整數中，數字2的個數為n*10^（n-1），其中n為正整數。

證明：易得，範圍內第i位為2的數有10^（n-1）個，其中i為不大於n的正整數，即範圍內第i位中的2有10^（n-1）個，則範圍內的2的個數為n*10^（n-1）。命題成立。

有個更簡單的證明方法：顯然，命題成立。

[1，x]裏有無窮多個2啊。。 完善一下題目吧

這不是數位DP裸題嘛……詳見ZJOI

#include& #include& #define LL long long #define REG register LL dp[15][15]; int a[15],len; LL dfs(int pos,int digit,int sum,int lead,int limit){ if(!pos) return sum; if((!lead)(!limit)dp[pos][sum]!=-1) return dp[pos][sum]; int top=limit?a[pos]:9; LL res(0); for(REG int i=0;i&<=top;++i) res+=dfs(pos-1,digit,sum+((!(lead(!i)))(i==digit)),lead(!i),(i==top)limit); if((!lead)(!limit)) dp[pos][sum]=res; return res; } LL solve(LL num,int digit){ len=0; while(num) a[++len]=num%10,num/=10; memset(dp,-1,sizeof(dp)); return dfs(len,digit,0,1,1); } int main(){ LL a,b; scanf("%lld %lld",a,b); for(REG int i=0;i&<=9;++i) printf("%lld ",solve(b,i)-solve(a-1,i)); }

找到代碼了，這是解決 [公式] 中各數碼出現的次數，時間複雜度 [公式]

核心思路是把數字當字元串然後建立Trie樹利用重複部分做記憶化搜索(本質上就是DP啦)

推薦閱讀：
相關文章