hihoCoder
给定一个数 x，设它十进制展从高位到低位上的数位依次是 a0, a1, ..., an - 1，定义交错和函数：
http://www.candesoft.com/blog/?p=234
Read full article from hihoCoder
给定一个数 x，设它十进制展从高位到低位上的数位依次是 a0, a1, ..., an - 1，定义交错和函数：
f(x) = a0 - a1 + a2 - ... + ( - 1)n - 1an - 1
例如：
f(3214567) = 3 - 2 + 1 - 4 + 5 - 6 + 7 = 4
给定 l, r, k，求在 [l, r] 区间中，所有 f(x) = k 的 x 的和，即：
输入
输入数据仅一行包含三个整数，l, r, k(0 ≤ l ≤ r ≤ 1018, |k| ≤ 100)。输出
输出一行一个整数表示结果，考虑到答案可能很大，输出结果模 109 + 7。提示
对于样例 ，满足条件的数有 110 和 121，所以结果是 231 = 110 + 121。http://www.candesoft.com/blog/?p=234
很明显是动态规划题目（题目tag），其实也是因为f(x)函数的特性。我们可以把一个数字（例如四位数）拆成a0,a1,a2,a3来表示。其中a0表示高位，a1表示低位。这个时候f(a0,a1,a2,a3)=a0-f(a1,a2,a3)。这点是肯定可以知道的。
为了方便，我们定义题目给的公式为小写f，而我们自己的递推式使用大写的F和G。
F(i,j,k)表示i为整数，最高位为j，要求f(x)值为k的所有范围内的x的和MOD 10^9+7。例如F(2,3,4)表示的是f(x)值为4的从00-39范围内所有x的和MOD 10^9+7。
再定义G(i,j,k)表示表示i为整数，最高位为j，要求f(x)值为k的所有范围内的x的数量【注意这个数量可能非常大，不过__int64是可以存的下的】。例如G(2,3,4)表示f(x)值为4的从00-39范围内有多少个满足这样条件的数。
这里我们需要重点强调一下关于0的事情，从刚刚的定义很多人会认为如果是0-9999范围的数，满足f(x)=5，那么他们的和应该是F(4,9,5) ，这是不对的。注意了，我们的F(i,j,k)函数及G(i,j,k)函数都是允许以0开头的数字，换句话说，F(4,9,5)表示的数据范围实际上是0000-9999，为什么0是允许的呢？因为从递推式上看（一会儿给出），这些数字将会成为未来数字的子串，这样才能满足之前提到的f(a0,a1,a2,a3)=a0-f(a1,a2,a3)。
【再次强调注意0开头，0开头不是没有意义的，而且不是所有0开头在所有情况下f(x)都是一样的，比如001和0001他们的f(x)值是完全不一样的，这也是这题的第一个坑点。】
下面给出递推式：
F(i,j,k)=( F(i,j-1,k)+f(i-1,9,j-k)+10^(i-1)*j*G(i,9,j-k) )MOD (10^9+7)
F(i,j,k)=( F(i,j-1,k)+f(i-1,9,j-k)+10^(i-1)*j*G(i,9,j-k) )MOD (10^9+7)
稍微解释一下这个递推式，以F(4,5,6)显然0000-5999的是由0000-4999加上5000-5999。那么5000-5999怎么求呢？显然就是由底下的数字000-999中满足f(x)值为(j-k)的数字的和来组成，与此同时还要算上5000*他们的数量，因为你给每个满足条件的数字都扣了个5的帽子嘛，他们实际上是5000-5999但是你只加了000-999。
G(i,j,k)也比较好算，直接给出式子：G(i,j,k)=G(i,j-1,k)+G(i-1,9,j-k)
有了这样的递推式，我们似乎是不够的，因为题目给的是任意区间的两个数内。那么我们怎么转换呢？
其实可以转换为求(0到l-1的和)以及(0到r的和)这样，这两个和相减不就是题目要求的了？
怎么算0到l-1呢，
我们以1234为例，首先有0-999【注意这部不是直接由F拿到的】，然后算1000-1199，然后算1200-1229，然后算1230-1233。（这里之所以处理成l-1是因为代码中编写会更为容易）
http://blog.csdn.net/labud/article/details/43448449Read full article from hihoCoder
