描述
输入
输入数据仅一行包含三个整数，l, r, k(0 ≤ l ≤ r ≤ 1018, |k| ≤ 100)。
输出
输出一行一个整数表示结果，考虑到答案可能很大，输出结果模 109 + 7。
提示
对于样例 ，满足条件的数有 110 和 121，所以结果是 231 = 110 + 121。
更多样例
Input
4344 3214567 3
Output
611668829
Input
404491953 1587197241 1
Output
323937411
Input
60296763086567224 193422344885593844 10
Output
608746132
Input
100 121 -1
Output
120
样例输入
100 121 0
样例输出
231
题解
设\(dp[i][j][k]\)为处理到第i位，当前数的位数为j，交错和为k。
import java.io.*;
import java.util.*;
public class Main {
static class pair {
long x, y;
pair(long tx, long ty) {
super();
x = tx;
y = ty;
}
pair() {
x =y = 0;
}
}
static final int mod = 1000000007;
static pair dp[][][] = new pair[25][25][405];
static long l, r, ten[] = new long[20];
static int bit[] = new int[20], k;
static pair dfs(int pos, int s, boolean zero, boolean flag, int sum) {
if (pos < 0)
return new pair(sum == k ? 1 : 0, 0);
if (!zero && !flag &&dp[pos][s][sum+200].x != -1)
return dp[pos][s][sum+200];
int end = (flag ? bit[pos] : 9);
pair ans= new pair(),tmp=new pair();
for (int i = 0; i <= end; i++) {
if (zero) {
if (i == 0)
tmp = dfs(pos - 1, 0, true, flag && (i == end), 0);
else
tmp = dfs(pos - 1, 1, false, flag && (i == end), i);
} else {
tmp = dfs(pos - 1, s + 1, false, flag && (i == end), sum + ((s & 1) == 1 ? -i : i));
}
ans.x = (ans.x + tmp.x) % mod;
ans.y = (ans.y + tmp.y + tmp.x * i * ten[pos] % mod) % mod;
}
if (!flag && !zero)
dp[pos][s][sum+200] = ans;
return ans;
}
static long solve(long n) {
if (n <= 0)
return 0;
int len = 0;
while (n > 0) {
bit[len++] = (int)(n % 10);
n /= 10;
}
return dfs(len - 1, 0, true, true, 0).y;
}
public static void main(String[] args) {
ten[0] = 1;
for (int i = 1; i <= 18; i++)
ten[i] = ten[i - 1] * 10 % mod;
Scanner sc = new Scanner(new InputStreamReader(System.in));
while (sc.hasNext()) {
for (int i = 0; i < 25; i++)
for (int j = 0; j < 25; j++)
for (int h = 0; h < 405; h++)
dp[i][j][h] = new pair(-1, 0);
long l = sc.nextLong(), r = sc.nextLong();
k = sc.nextInt();
System.out.println((solve(r)-solve(l-1)+mod)%mod);
}
sc.close();
}
}