【HIHOCODER 1033 】 交错和（数位DP）
2024-09-02 11:44:38
描述
输入
输入数据仅一行包含三个整数，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();
}
}
最新文章
- luogg_java学习_08_设计模式_API
- a questions
- [Leetcode]Reverse Integer
- 从零开始学CSRF
- 快速幂 --- CSU 1556: Jerry's trouble
- while循环语句的使用
- hdu------(4300)Clairewd’s message(kmp)
- STL之迭代器
- express源码剖析2
- Linux的各种命令(android adb shell)
- [转]CharacterController与Rigidbody
- Crowd安装和破解
- 一道变态的js题
- ceph hammer 0.94.10手动部署方法Ceph Hammer版(0.94.10)手动部署for CentOS 7.x
- 【LOJ6284】数列分块8
- LOJ #559. 「LibreOJ Round #9」ZQC 的迷宫
- linux 修改hosts文件
- vue 点击一个div，使input获得焦点
- Ubuntu 14.10 下Hadoop代码编译问题总结
- 1084. Broken Keyboard (20)-水题