Problem

http://acm.sjtu.edu.cn/OnlineJudge/problem/1398

题目描述

给定一个数字，他在十进制下从高位到低位一次是n0, n1, n2, n3,…

那么定义它的“差和”为n0-n1+n2-n3+…

如：十进制数字abcdefg，每个字母代表一个位，那么差和为a-b+c-d+e-f+g。

所以十进制数字1234567差和为1-2+3-4+5-6+7=4

现在给你们一个闭区间[m, n]，请求出区间内差和为x的数字个数。

输入格式

输入只有一行，三个数字，m n x

30%: 0<= m <= n <=10^3, 50%: 0<= m <= n <=10^8, 100%: 0<= m <= n <=10^18

-100<= x <=100

输出格式

输出只有一个数字，表示区间内差和为x的数字的总和mod1000000007的结果。

Sample Input

100 111 1

Sample Output

211

Analysis

相当捉急的题目。

令F[i][first digit][j]

表示长度为i的数（包括010 这个3位数），第一位为first digit时，差和为j的个数

令g[i][first digit][j]

表示长度为i的数（包括010 这个3位数），第一位为first digit时，差和为j的数之和

之后可以利用简单dp推出f、g

主要难点在于如何把实际的一些数分拆出来。

简化，我们只考虑统计1～n之间满足条件数的和，之后利用减法就能得到区间结果。

（函数calc）这个是不包括有前导0的情况的。

比如说234。我们可以分拆成 0 + [00,99] , 100~199 , 2+[00,34]

如果知道[00,34]有k个数（如何求出这k个数见calcnum）满足我们对这个区间的需求，那么234在2+[00,34]内所有数之和就是[00,34]所有数之和 + 200 *k

然而，我们在去掉头一位时，不可避免地需要统计[00,99]区间内的情况，它是与calc函数不同的。因此我们使用了一个calc2函数来解决这个问题。

取余坑。

Code