| 一台打字机准备将1到10^n的数依次打出。在打印过程中，这台打字机出现了一个故障：数字“3”打不出来。因此，所有含有数字“3”的数都没有被正确地打出。试问没有被正确打出的数一共有多少个。 |
| n<=1000 |
这道题目很显然，我们要想出来一种不重也不漏的方法
我是这样写的 我们从高到低枚举每一位
强制这一位选3，强制这一位前的全部不选，这一位后的随意
比如说对于第i位 那么对答案的贡献就是9^(i-1)*10^(n-i)
我们预处理出来ten[i]数组表示i个10连乘的结果，nig[i]表示i个9连乘的结果
就可以表示为nig[i-1]*ten[n-i]
PS:写这道题只当练习高精度了，我还是喜欢用结构体写高精度，美滋滋
原文：http://www.cnblogs.com/something-for-nothing/p/7886739.html