P4999 烦人的数学作业
大意
求 \([L,R]\) 的数字的数字和。（\(1\le L, R \le 10 ^ {18}\)）
思路
首先，显然，数位 DP，很裸的一道题。
我们做如下定义 \(f[pos][sum][lim][zero]\) 为在 \(pos\) 下，当前数字和为 \(sum\)，是否有限制，是否为前导 \(0\)。
那么我们做记忆化搜索（正着太麻烦了，感觉还是搜索比较形象），于是每次只需要累加下一层的答案即可。
注意当前的位置能取到的值，如果没有 \(lim\) 的限制的话，那么直接取到 \(9\) 显然没有问题，但是如果有限制，只能取到和原数组这个位置的元素一样大的值，即 maxx = lim ? a[pos] : 9。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int MOD = 1e9 + 7;
#define ll long long//pos sum limit zero
ll f[20][200][2][2];
ll a[20], len; ll dp(int pos, int sum, int lim, int zero){if(pos == len){return sum % MOD;}if(~f[pos][sum][lim][zero]){return f[pos][sum][lim][zero] % MOD;}int ans = 0;int maxx = lim ? a[pos] : 9;for(int i = 0;i <= maxx;i ++){int nw = (i == 0) && zero;ans = (ans + dp(pos + 1, sum + i, lim && (i == maxx), nw)) % MOD;}return (f[pos][sum][lim][zero] = ans) % MOD;
}ll solve(ll x){memset(f, -1, sizeof(f));len = 0;while(x){a[len ++] = x % 10;x /= 10;}reverse(a, a + len);return dp(0, 0, 1, 1);
}int main(){ll L, R, T;cin >> T;while(T --){cin >> L >> R;cout << (solve(R) - solve(L - 1) + MOD) % MOD << '\n';}return 0;
}