一个最简单的方法来计算 \(f(N)\) ，那就是从 1 开始遍历到 N ，将 1 的个数加起来就是答案了。但是这个算法的效率， \(O(N*log2(N))\) 。

那么让我们来分析一下对于一个指定的 N ，如何得到一个规律来求得每一位上所有出现 1 的可能性，看看能不能总结出什么规律。

先看一位数的情况。 如果 \(N=3\) ，那么从 1 到 3 的所有数字： \(1,2,3\) 。只有个位数字上可能出现 1 ，而且只出现了一次。那么如果 N 为个位数，且 \(N>=1\) ，那么 \(f(N)=1\) 。

再看两位数的情况。 如果 \(N=13\) ，那么个位数出现 1 的次数有两次： 1 和 11 ，十位数出现 1 的个数有 4 次： \(10,11,12,13\) ，所以 \(f(N)=2+4=6\) 。 同理可得：

• \(f(13)\) =个位数上 1 的个数+十位数上 1 的个数= \(2+4=6\)

• \(f(23)\) =个位数上 1 的个数+十位数上 1 的个数= \(3+10=13\)

• \(f(33)\) =个位数上 1 的个数+十位数上 1 的个数= \(4+10=14\)

• 。。。

• \(f(93)\) =个位数上 1 的个数+十位数上 1 的个数= \(10+10=20\)

接着分析三位数。 如果 \(N=123\) ： 个位数上出现 1 的个数为 13 个： \(1,11,21，...，91,101,111,121\) 。 十位数上出现 1 的个数为 20 个： \(10~19,110~119\) 。 百位数上出现 1 的个数为 24 个： \(100~123\) 。 则 \(f(123)\) =个位数上 1 的个数+十位数上 1 的个数+百位数上 1 的个数= \(13+20+24=57\) 。

根据上面的一些尝试，我们可以推断出下面的一般情况： 如果我们要计算百位数上出现 1 的个数，它将受到三个因素的影响：百位数上的数字，百位以下的数字，百位以上的数字。 如果百位数上的数字为 0 ，则可以知道，百位上可能出现 1 的次数由更高位位决定，比如 12013 ，则可以知道百位出现 1 的情况可能是 \(100~199,1100~1199,2100~2199，...，11100~11199\) ，一共 1200 个。也就是更高位数字(12)决定，并且等于更高位数字(12) *当前位数(100) 。

如果百位数上的数字为 1 ，则可以知道，百位上可能出现 1 的次数不仅受更高位影响，还受低位影响。例如 12113 ，受更高位影响，百位出现 1 的情况是 \(100~199,1100~1199,2100~2199，...，11100~11199\) ，一共 1200 个。但是它还受低位影响，百位出现 1 的情况是 12100~12113 ，一共 114 个，等于低位数字 (123) + 1 。

如果百位数上的数字大于 1 ，则百位上可能出现 1 的次数也仅由更高位决定。比如 12213 ，则百位上出现 1 的可能性为 \(100~199,1100~1199,2100~2199，...，11100~11199，12100~12199\) ，一共 1300 个，并且等于更高位数字+ \(1(12+1)\) *当前位数 (100) 。

则我们把百位数推广到任何位数上，就可以高效的计算出 \(f(N)\) ，时间复杂度只要 \(O(ln(N)/ln(10)+1)\) 。

看到这样的题目，理所当然先想到的方法就是递推，但是该怎么推呢？ 这个矩阵是对称的，那么我们只有计算四分之一的部分就可以了(对称)。

我们先定义三个数组， F[] , G[] 和 L[] 。

• F[] 数组所存的是 \(2*n\) 格子所有走法的数量。

• G[] 数组所存的是含有顶点那部分的那个格子为起点的所有走法的数量。

• L[] 数组所存的是 2 的所有次方的结果。

然后此题的关键部分就是一点：我们可以发现每列都只有 2 个格子，所以当你往左边走的时候，如果右边还有格子，那么你就只能一列走一格，不然回不到后边，如果不理解这一点就仔细想想，自己模拟一下就知道了。往右边同理。

既然理解了上面这一点，在这里我就直接讲推出后的过程了，以当前格子 \(2*n(n>3)\) 为例。 首先我们取最坐上角的那个格子为起点，那么此点的走法有三种：

1、往下走，那么走法数= \(2*g[n-1]\) 。

2、往右走再往左走，那么走法数= \(2*2*g[n-2]\) 。

3、往右走再往右走(最后回到最左端)，那么走法数= \(L[n-1]\) 。

接下来我们取除上种情况的其他任意一个格子为例。 假设我们取的格子位置是：他的左边有x个格子，右边有 n-1-x 个格子。 则，走法只有两种：

1、第一步往左走，那么他只能走完左边的才能走右边的。走法数= \(L[x]*2*g[n-1-x]\) 。

2、第一步往右走，那么他只能走完右边的才能走左边的。走法数= \(L[n-1-x]*2*g[x]\) 。