打表

打表

给定一个十进制的正整数（1<=n<=10000），写下从1到n的所有整数，然后数一下其中出现的数字“1”的个数

例如当n=2时，写下1，2，这样只出现1个“1”；当n=12时，写下1，2，3，4，5，6，7，8，9，10，11，12，这样出现5个“1”。

输入

每行有一个数字n

输出

输出占一行，每行一个整数，即“1”的个数

样例输入

2

12

样例输出

1

5

这里用到打表法：打表是一种典型的用空间换时间的技巧，主要用在程序中一次性计算出所有需要用到的结果，之后的查询直接取这些结果。

打一张表格，把需要的东西都保存下来

代码实现：

这里再看一道例题：

题目描述：

字符串APPAPT中包含两个单词“PAT”，其中第一个PAT是由第二位（P）、第四位（A）和第六位（T）组成的；第二个PAT是由第三位（P）、第四位（A）和第六位（T）组成的。

输入：

一个字符串

输出：

输出包含多少个PAT。由于结果可能比较大，因此只输出对1000000007取余的结果

样例输入：

APPAPT

样例输出：

2

打表得：

技巧: 问题可以转换为，对于字符串中每个A，计算它左边P的个数与右边T的个数的乘积，然后把所有A的这个乘积相加就是答案。