J - Junior Mathematician Gym - 102452J（数位DP）

本文主要是介绍J - Junior Mathematician Gym - 102452J（数位DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss said, “Mathematics is the queen of the sciences—and number theory is the queen of mathematics.” Number theorists study prime numbers as well as the properties of objects made out of integers or defined as generalizations of the integers.

Portrait of Carl Friedrich Gauss by C.A. Jensen. Public Domain.
Chandra is a junior mathematician who has just guaduated from university and she specializes in number theory. It has always been her ambition to become as famous a mathematician as Gauss. In her recent work, she invented a new function f(x) for a postive integer x during her recent research in number theory. Let k be the number of digits in the decimal representation of x, and d(x,i) (1≤i≤k) be the i-th digit of x in its decimal representation. Then
f(x)=∑i=1k−1∑j=i+1kd(x,i)⋅d(x,j)
Chandra has also found a mysterious integer m. She thinks that positive integers which satisfy the property x≡f(x)(modm) may be very important for her research. She wants to find out the number of such integers x which also satisfy L≤x≤R. She only needs to know that number modulo 109+7, which is another mysterious integer she has found during her research. Unfortunately, the numbers L and R can be very large and it is not feasible to solve that problem by hand, even for a mathematician. In order to publish her paper and become a well-known mathematician, Chandra asks you, a famous programmer, to help her overcome this obstacle in her research.

Input
The input contains multiple cases. The first line of the input contains a single positive integer T, the number of cases.

For each case, the first line and the second line of the input each contains a single integer, L and R (10≤L≤R<105000), respectively. The third line of the input contains a single integer m (2≤m≤60).

It is guaranteed that the sum of the number of digits of R over all cases doesn’t exceed 5000.

Output
For each case, print a single integer on a single line, the number of integers x satisfying the required conditions, modulo 109+7.

Example
Input
2
10
50
17
33
33
3
Output
2
1

题意：
问多少数满足 $f[x]\equiv x\mathrm{m}\mathrm{o}\mathrm{d}m$
$f[x]$代表$x$的数位间乘积

思路：
很容易看出来是数位DP，求两个数相等，可以想到作差。
定义$dp[len][sum][minus]$代表遍历到了第$len$位，之前位的数位和为$sum$，之前位的$f[x]$与$x$的差为$minus$的方案数。

那么遍历到最后$minus=0$则代表这是个可行方案。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 5005;
const int mod = 1e9 + 7;
char s[maxn],t[maxn];
int p[maxn],dp[maxn][61][61];
int n,m;int dfs(int len,int sum,int minus,int limit) {if(len == n) {return minus == 0;}if(dp[len][sum][minus] != -1 && !limit) {return dp[len][sum][minus];}int up = limit ? s[len] - '0' : 9;int ans = 0;for(int i = 0;i <= up;i++) {ans = (ans + dfs(len + 1,(sum + i) % m,((minus + i * sum - i * p[n - len - 1]) % m + m) % m,limit && i == up)) % mod;}if(!limit) return dp[len][sum][minus] = ans;return ans;
}void init() {p[0] = 1;for(int i = 1;i <= n;i++) {p[i] = 1ll * p[i - 1] * 10 % m;}for(int i = 0;i <= n;i++) {for(int j = 0;j <= 60;j++) {for(int k = 0;k <= 60;k++) {dp[i][j][k] = -1;}}}
}int main() {int T;scanf("%d",&T);while(T--) {scanf("%s",s);scanf("%s",t);scanf("%d",&m);n = strlen(s);init();int sum = 0,f = 0,pre = 0;for(int i = 0;i < n;i++) {f += sum * (s[i] - '0');sum += s[i] - '0';f -= p[n - i - 1] * (s[i] - '0');f = (f % m + m) % m;}if(f == 0) pre = 1;int ans = -dfs(0,0,0,1) + pre;n = strlen(t);for(int i = 0;i < n;i++) {s[i] = t[i];}init();ans = ((ans + dfs(0,0,0,1)) % mod + mod) % mod;printf("%d\n",ans);}return 0;
}

这篇关于J - Junior Mathematician Gym - 102452J（数位DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---